C ++ - удаление узла в дереве AVL

Question

В настоящее время я пытаюсь реализовать дерево AVL в C ++, пока что я сделал почти все, кроме удаления узла.

1) Может ли кто-нибудь подтвердить, что мой алгоритм удаления узла правильный?

• Найти узел для удаления в дереве
• если узел имеет 0 дочерних элементов: удалить узел
• иначе, если у узла есть 1 дочерний элемент: удалите узел и повторно свяжите его дочерний элемент
• else (2 дочерних элементов): найдите его преемника и поменяйте местами узел для удаления с его преемником. затем повторите шаги, чтобы удалить узел (который теперь там, где был его преемник).
• Перебалансировать дерево после вставки (это рекурсивно сбалансирует дерево ...)

Я сделал это, но часть, в которой я не уверен, - это этап, на котором я удаляю узел. Должен ли я также удалить ссылку на узел, или она будет управляться? (Поскольку я передал параметр Node * &, но преемником является только Node * в функции ...)

Я не уверен, что я супер ясен, дайте мне знать, если вам нужно больше деталей.

(я бы выложил какой-нибудь код, но, к сожалению, я говорю по-французски, так что я думаю, вы многого из этого не поймете)

Answer 1

Если узел был создан с использованием 'new', его необходимо явно удалить, абсолютно. У них вопрос будет , где . Если вы удаляете узел (предполагается, что содержимое узла никому не нужно), вам также следует удалить сам узел после завершения удаления узлов из дерева.

Теперь ссылка на узел - это другое дело. Если ссылка является артефактом определения аргумента метода, вам не нужно ничего с этим делать. Ссылка была создана в стеке, чтобы помочь с вызовом метода. Если я помню мой C ++, ссылки никогда не могут быть нулевыми, что означает, что вам никогда не придется извиняться (плохая шутка), никогда не придется их удалять.

[EDIT] ОП говорит: «Потому что я передал параметр Node * &, но преемником является только Node * в функции ...)», поэтому я предположил, что вы имели в виду нечто вроде:

void removeNode(Node*& node) 

, который затем вызывается с помощью

void foo()
{
    Node* n = new Node();
    // for example
    removeNode(n);
}

Мой C ++ немного устарел, но идея здесь в том, что 'n' - указатель, а тип аргумента removeNode () - это ссылка на указатель. Вызывающая сторона не знает, что ссылка задействована, она просто передает 'n', ожидая, что тип arg будет указателем на узел (Node *). Компилятор создает ссылку как обертку вокруг аргумента, поэтому только вызываемый объект знает о ссылке. Поскольку ссылка создается в стеке, она будет правильно управляться при возврате removeNode (). Узел, на который указывает 'n', все еще необходимо удалить, вопрос в том, какой код должен его обрабатывать.

Первой мыслью было бы, чтобы 'removeNode ()' сделал это. Одна проблема заключается в том, что он имеет только ссылку на него, и если вы удалите указатель (цель ссылки), ссылка будет нулевой, что является плохой идеей / недопустимо. Просто мысль о синтаксисе, чтобы попытаться это заставило меня съежиться.

Итак, сделайте для этого клиентский код, например:

void foo()
{
    Node* n = new Node();
    // for example
    removeNode(n);
    delete n;
}

В основном , вам нужен план для области действия ваших указателей узлов. Пока это согласованно, вы можете сделать это несколькими различными способами. Если вы хотите, чтобы removeNode () обрабатывал удаление, измените тип аргумента на указатель вместо ссылки и документируйте вызов, так что ожидается, что он одновременно удалит узел из дерева и удалит также память.

Answer 2

Сложность вашего вопроса в том, что «удаление ссылки на узел» на самом деле довольно расплывчато: в зависимости от того, что вы считаете «удалением ссылки», ответ может быть «да» или «нет».

Как я понимаю, вы собираетесь "удалить ссылку на узел" как часть перерисовки дерева.Важной частью является тот факт, что ваш метод получает указатель узла как Node *&: с этим ваш метод не просто получает указатель на узел, находящийся под пристальным вниманием, он получает ссылку на то, где этот указатель хранится вродительский узел .Вы должны изменить эту ссылку, чтобы сохранить нетронутую связь с деревом.

Так что, если ваш метод делает что-то вроде этого:

void deleteNode (Node*& node) {
    if (node is the right one to delete) {
        Node * tmp = node;
        node = node->successor;
        delete node;
    }
    else
        deleteNode(node->successor);
}

назначение node = node->successor фактически изменяет предыдущие узлыпреемник поля.Без этого назначения ваша древовидная структура была бы повреждена, так как поле преемника предыдущих узлов указывало бы на теперь освобожденный узел.

Answer 3

Если вы кодируете в стандартном C ++, то для вас ничего не будет "управляемым". Если вы используете умные указатели, то они позаботятся о том, чтобы вы освободили их.

Что касается вашего интерфейса, я предлагаю функцию remove(), которая берет указатель на удаляемый узел. Тогда вам не нужно беспокоиться о поиске узла, как он задан. Напишите хотя бы функцию find(), чтобы клиенты могли сами найти узел.

Наконец, я не уверен, что следую вашему третьему случаю, когда удаляемый узел имеет двух детей. В дереве AVL, когда узел удаляется как два потомка, вы можете поменять его местами с крайним правым потомком левого поддерева узла, который нужно удалить. После замены у удаляемого узла будет ровно один или ноль дочерних элементов, поэтому вы существенно сократили проблему до этих двух случаев.

Например:

            20
     40            15
  60    35     18       10
80    38  30 19  17   13   8

В приведенном выше дереве, если вы хотите удалить узел 20, вы меняете его на узел 30 (дочерний узел 35):

            30
     40            15
  60    35     18       10
80    38  20 19  17   13   8

А затем удалите узел 20 как дочерний узел. Если бы не было узла 30, то самым правым дочерним элементом левого поддерева был бы узел 35, и вы бы поменялись с ним узлом 20. Затем вам нужно будет удалить узел с одним ребенком, что вы знаете, как это сделать.

Обратите внимание, что пока вы не закончите удаление, дерево находится в несогласованном состоянии. Это важно, если вы работаете одновременно.