Простое удаление дерева AVL работает только иногда

Question

Я работаю над деревом 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;

и временный указатель действует в поведении, с которым я не знаком, или если вся моя реализация неверна. Я знаю, что где-то пропали узлы, потому что утечка памяти показывает, что эти два пропавших узла никогда не удаляются.

Answer 1

Мне интересно, имеет ли это какое-то отношение к линиям

Да. Node<ItemType>* & temp = node->rightChild; говорится temp это псевдоним для node->rightChild, Итак while цикл модифицирует node->rightChild и вы потеряете ручку для первоначального правильного ребенка.

Возьмите обычный указатель и проведите его по правому поддереву, пока не дойдете до родителя его самого маленького члена. Затем получите значение наименьшего члена, чтобы скопировать его в node->itemи удалите левого потомка родителя.