Java RB树删除

Question

我正在尝试实现 T. H. Cormen 的 RB Tree 算法，但找不到解决我的问题的方法。当我想删除一些节点时，出现 NullPinterException。这是我的代码:

        public void rbTreeDelete(RBNode z) {
        RBNode y = z;
        RBNode x = new RBNode();
        Color yOriginalColor = y.color;
        if(z.left == null) {
            x = z.right;
            rbTransplant(z, z.right);
        }
        else {
            if(z.right == null) {
                x = z.left;
                rbTransplant(z, z.left);
            }

            else {
                y = treeMinimum(z.right);
                yOriginalColor = y.color;
                x = y.right;
                if(y.p == z) {
                    x.p = y;
                }
                else {
                    rbTransplant(y, y.right);
                    y.right = z.right;
                    y.right.p = y;
                }
                rbTransplant(z, y);
                y.left = z.left;
                y.left.p = y;
                y.color = z.color;
            }
            if(yOriginalColor == Color.Black) {
                rbDeleteFixup(x);
            }
        }
    }
    public void rbTransplant(RBNode u,RBNode v) {
        if(u.p == null) {
            root = v;
        }
        else {
            if(u == u.p.left){
                u.p.left = v;
            }
            else {
                u.p.right = v;
            }
        }
        if (v != null) {
            v.p = u.p;
        }
    }
    public void rbDeleteFixup(RBNode x){
        while(x !=root && x.color == Color.Black) {
            if(x == x.p.left) {
                RBNode w;
                w = x.p.right;
                if(w.color == Color.Red) {
                    w.color = Color.Black;
                    x.p.color = Color.Red;
                    leftRotate(x.p);
                    w = x.p.right;
                }
                if(w.left.color == Color.Black && w.right.color == Color.Black) {
                    w.color = Color.Red;
                    x = x.p;
                }
                else {
                    if(w.right.color == Color.Black) {
                        w.left.color = Color.Black;
                        w.color = Color.Red;
                        rightRotate(w);
                        w = x.p.right;
                    }
                    w.color = x.p.color;
                    x.p.color = Color.Black;
                    w.right.color = Color.Black;
                    leftRotate(x.p);
                    x = root;
                }
            }
            else {
                RBNode w = x.p.left;
                if(w.color == Color.Red) {
                    w.color = Color.Black;
                    x.p.color = Color.Red;
                    rightRotate(x.p);
                    w = x.p.left;
                }
                if(w.right.color == Color.Black && w.left.color == Color.Black) {
                    w.color = Color.Red;
                    x = x.p;
                }
                else {
                    if(w.left.color == Color.Black) {
                        w.right.color = Color.Black;
                        w.color = Color.Red;
                        rightRotate(w);
                        w = x.p.left;
                    }
                    w.color = x.p.color;
                    x.p.color = Color.Black;
                    w.left.color = Color.Black;
                    leftRotate(x.p);
                    x = root;
                }
            }
        }
        x.color = Color.Black;
    }       

行中出现异常:

            if(y.p == z) {
                x.p = y;
            }

in rbTreeDelete method, when i try to delete node with 9 value. My test script:

                t.insert(7);
            t.insert(5);
            t.insert(8);
            t.insert(3);
            t.insert(9);
            t.insert(18);
            t.insert(32);
            t.rbTreeDelete(treeSearch(t.root, 32));
            t.rbTreeDelete(treeSearch(t.root, 9));
            t.rbTreeDelete(treeSearch(t.root, 8));
            t.rbTreeDelete(treeSearch(t.root, 5));
            t.rbTreeDelete(treeSearch(t.root, 8));
            t.rbTreeDelete(treeSearch(t.root, 3));

感谢您的任何建议。

编辑:树最小代码:

        public RBNode treeMinimum(RBNode x) {
        while(x.left != null){
            x = x.left;
        }
        return x;
    }

Answer 1

所以，我认为问题出在下面的代码中:

在这里，您将“y”设置为从 z 右侧开始的树最小值(因为 z.right != null)，这很好。

但是，这个最小值并不能保证 y 将有一个正确的节点 (y.right != null)

我相信在尝试分配父节点值之前，由于 x 设置为 null，您可能会收到一个空指针。

else {
                y = treeMinimum(z.right);
                yOriginalColor = y.color;
                x = y.right;
                if(y.p == z) {
                    x.p = y;
                }