1

これは、削除するノードに 2 つの子がある最後のケースです。何が間違っているのかわかりません。助けてください。

    //BTNode has two children
    else if (u.getLeft() != null && u.getRight() != null){
        //if node to delete is root
        BTNode<MyEntry<K,V>> pred = u.getRight();


        while (pred.getLeft().element() != null){
            pred = pred.getLeft();
        }


        BTNode<MyEntry<K,V>> predParent = pred.getParent();
        if (!hasRightChild(pred)){
            predParent.setLeft(new BTNode<MyEntry<K,V>>(null,predParent,null,null));}
        if (hasRightChild(pred)){
            BTNode<MyEntry<K,V>> predChild = pred.getRight();
            predParent.setLeft(predChild);
            predChild.setParent(predParent);
        }


        return returnValue;

わかりましたので、このように変更しますか??

        u.setElement(succ.element());



        BTNode<MyEntry<K,V>> succParent = succ.getParent();
        if (!hasLeftChild(succ)){
            succParent.setRight(new BTNode<MyEntry<K,V>>(null,succParent,null,null));}
        if (hasLeftChild(succ)){
            BTNode<MyEntry<K,V>> predChild = succ.getLeft();
            succParent.setRight(predChild);
            predChild.setParent(succParent);
        }


        return returnValue;
4

2 に答える 2

1

ウィキペディアから：

2 つの子を持つノードの削除: 削除するノードを N と呼びます。N を削除しないでください。代わりに、順序どおりの後続ノードまたは順序どおりの先行ノード R を選択します。N の値を R の値に置き換えます。 、次に R を削除します。

したがって、たとえば左の子を取り、そのサブツリーの右端の葉を見つけて、削除するノードの情報を葉の情報に置き換え、その葉を簡単に削除します。

サブツリーから右端の葉を返す関数を作成したい場合があります。

于 2012-12-07T00:58:21.387 に答える