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

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

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

1

Решение

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

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

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

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]