1

私はAVLツリーに取り組んでいます。私の削除は、時々正しく機能するようです。こんな感じの木を作りました

          f
        /   \
       e     j
      /    /   \
     a    h     s

を順番に挿入してf e h s j aください。インサートとバランシングで正しく機能していることはわかっています。

a、またはj、またはh、またはs、またはを削除するとe、すべて正常に動作します。を削除するfと、 に置き換えfられhます。これは正しいのですが、 と を失いjますs。

これは、最初に呼び出される関数です。

    void remove(const ItemType& item)
    {
        if(root == NULL)
            return;
        else
        {
            remove(root, item);
        }
    };

最初の関数はこれを呼び出して、正しいノードを再帰的に見つけます。

    void remove(Node<ItemType>* & node, const ItemType& item)
    {
        if(item > node->item)
        {
            if (node->rightChild == NULL)
            {
                return; // there is nothing here to remove
            }
            else
            {
                // recurse to next node
                remove(node->rightChild, item);
            }
        }
        else if (item < node->item)
        {
            if (node->leftChild == NULL)
            {
                return; // there is nothing here to remove
            }
            else
            {
                // recurse to next node
                remove(node->leftChild, item);
            }
        }
        else if (node->item == item)
        {
            remove(node);
        }

        if (node != NULL)
            node->updateHeight();
    };

これは最後に呼び出される関数です。これは、削除とスワップが行われる場所です。

    void remove(Node<ItemType>* & node)
    {
        if (node->rightChild == NULL && node->leftChild == NULL)
        {
            delete node;
            node = NULL;
        }
        else if (node->rightChild == NULL)
        {
            Node<ItemType>* temp = node;
            node = node->leftChild;
            delete temp;
        }
        else
        {
            Node<ItemType>* & temp = node->rightChild;
            while (temp->leftChild != NULL)
                temp = temp->leftChild;

            node->item = temp->item;
            delete temp;
            temp = NULL;
        }

        if(node != NULL)
            node->initializeHeight();
    };

ラインと関係あるのか気になる

            Node<ItemType>* & temp = node->rightChild;
            while (temp->leftChild != NULL)
                temp = temp->leftChild;

            node->item = temp->item;
            delete temp;
            temp = NULL;

一時ポインタがよくわからない動作をしている、または実装全体が間違っている場合。行方不明になった 2 つのノードが決して削除されないことをメモリ リークが示しているため、行方不明のノードがどこかにあることはわかっています。

4

1 に答える 1

2

ラインと関係あるのか気になる

はい。Node<ItemType>* & temp = node->rightChild;はtempの別名ですnode->rightChild。したがって、whileループが変更node->rightChildされ、元の右の子へのハンドルが失われます。

通常のポインターを使用して、その最小メンバーの親に到達するまで、右側のサブツリーをたどります。次に、最小のメンバーの値を取得して にコピーしnode->item、親の左の子を削除します。

于 2013-04-02T20:39:57.467 に答える