Java RB树删除

Question

我正在尝试从T. H. Cormen实现RB树alghoritm，并且找不到解决方案。有一个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; 
      } 

在rbTreeDelete方法，当我尝试删除节点9价值。我的测试脚本：

   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)); 

感谢您的任何建议。

编辑：treeMinimum代码：

 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; 
       }