0

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

这是 Successor 方法：

 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后如何删除它？

4

1 回答 1

0

您要删除的节点可能没有任何子节点。在这种情况下，您没有要重新设置的子树。

于 2013-05-05T11:07:02.523 回答