删除红黑树中的方法

Question

我在RB树中删除方法有问题。在x.parent=y.parent有一个NullPointerException。问题肯定是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，删除后?

Answer 1

要删除的节点可能没有任何子节点。在本例中，没有子树要表示。