0

RB ツリーの remove メソッドに問題があります。に 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た後、削除する方法は?

4

1 に答える 1