红黑树中的删除方法

我在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

红黑树中的删除方法

回答

相关问题