紅黑樹中的刪除方法

我在RB樹中刪除方法有問題。有一個NullPointerException在x.parent=y.parent。這個問題肯定是x=null，如果我在DeleteFixUp方法中使用這個x，那麼也有NullPointerException。我哪裏有錯誤？紅黑樹中的刪除方法

Element delete(Element DeleteNode) 
{ 

Element x=null; 

Element y=null; 

    if((DeleteNode.left==null)||(DeleteNode.right==null)) 
     y=DeleteNode; 
    else 
     y=Succesor(DeleteNode,root); 

    if (y.left != null) 
     x=y.left; 
    else 
     x=y.right; 

    x.parent=y.parent; 

    if (y.parent == null) 
     root = x; 
    else 
    if (y == y.parent.left) 
     y.parent.left = x; 
    else 
     y.parent.right = x; 
    if (y != DeleteNode) 
     DeleteNode.value = y.value; 

    if(!isRed(y)) 
    { DeleteFixUp(x);} 
    return y; 
}

這裏是接班人方法：

Element Succesor(Element x, Element root) 

{ 

    if(x.right != null) 
    { x=FindMin(x.right); 
     return x; 
       } 

    Element succ = null; 

    while (root != null) 
    { 
     if (_comparator.compare(x.value,root.value)==-1) 
     { 
      succ = root; 
      root = root.left; 
     } 
     else if ((_comparator.compare(x.value,root.value)==1)) 
      root = root.right; 
     else 
      break; 
    } 

    return succ; 
}

歐凱，我已經解決了這個問題，但我還有一個。我添加到我的代碼：

Element delete(Element DeleteNode) 
{ 

Element x=null; 

Element y=null; 

    if((DeleteNode.left==null)||(DeleteNode.right==null)) 
     y=DeleteNode; 
    else 
     y=Succesor(DeleteNode,root); 

    if (y.left != null) 
     x=y.left; 
    else 
     x=y.right; 
    //added to code 
    if (x == null) 
    {x = new Element(null);    
    x.kolor=0;   
    } 


    x.parent=y.parent; 

    if (y.parent == null) 
     root = x; 
    else 
    if (y == y.parent.left) 
     y.parent.left = x; 
    else 
     y.parent.right = x; 
    if (y != DeleteNode) 
     DeleteNode.value = y.value; 

    if(!isRed(y)) 
    { DeleteFixUp(x);} 
    return y; 
}

現在，我有一個問題，如何刪除這個x.value=null，刪除後？

來源

2013-05-05 Xwar

您正在刪除的節點可能沒有任何子節點。在這種情況下，你沒有子樹可以重新分區。

來源

2013-05-05 11:07:02

紅黑樹中的刪除方法

回答

相關問題