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