Причина назначения дочерних узлов после удаления из двоичного дерева поиска?

почему присваивание (p->rchild =, p->lchild =) происходит каждый раз, когда вызывается Delete(Node* p, int key)?

Если данные найдены, то цель состоит в том, чтобы иметь дерево, в котором на один узел меньше. Алгоритм будет использовать механизм замены значений, чтобы гарантировать, что фактически удаляемый узел всегда будет конечным узлом. Удаление листового узла состоит из двух действий:

1. Удаление из памяти;
2. Обновление его родителя, чтобы дочерний указатель, который ссылается на этот удаленный узел, был установлен на нулевой указатель.

Поскольку алгоритм рекурсивно обращается прямо к этому листовому узлу, он не может установить нулевой указатель на своего родителя, поскольку на данном этапе нет доступной ссылки на родительский узел. Для этого вызывающая сторона должна что-то сделать, поскольку у вызывающей стороны есть ссылка на родителя.

Поэтому, когда рекурсивный обход достигает конечного узла, он должен сообщить вызывающей стороне, что этот узел должен быть отсоединен. Он делает это, возвращая нулевой указатель, и соглашение заключается в том, что вызывающая сторона (чей текущий узел p является родителем) должна назначить возвращенный указатель соответствующему дочернему указателю. Таким образом, удаленный узел действительно отделяется от остальной части дерева.

На самом деле, я думал, что метод Delete(Node* p, int key) просто продолжает возвращаться без каких-либо мутаций, поэтому дерево не меняется.

Конечно, дерево должно как-то измениться, чтобы из него был удален узел. Изменение происходит в назначении на p->lchild или p->rchild

Я наткнулся на эту фразу:

Мы должны выполнять назначения после удаления, иначе у нас будут дубликаты узлов.

Это верно. Возьмем пример дерева:

                 7
                / \
               3   8
              / \   \
             1   5   9
            /   / \ 
           0   4   6

Теперь давайте посмотрим, что произойдет, если мы позвоним Delete(root, 3). p указывает на узел со значением 7. Идем влево рекурсивным вызовом:

p->lchild = Delete(p->lchild, key);

В контексте рекурсивного выполнения мы получаем новый p, который указывает на узел со значением 3. Это значение, которое мы ищем, поэтому мы попадаем во внешний блок else. Поскольку высоты поддеревьев ниже этого узла равны, мы попадаем во внутренний блок else. Там мы назначаем:

q = InSucc(p->rchild);

Этот q будет ссылаться на узел со значением 4. И теперь происходит дублирование. Копируем данные из q в p. Это сводится к удалению значения 3 из дерева:

p->data = q->data;

Но теперь у нас есть в два раза больше значения 4 в дереве.

                 7
                / \
               4*  8
              / \   \
             1   5   9
            /   / \ 
           0   4*  6

Таким образом, алгоритм спускается к (правому) дочернему элементу и теперь пытается удалить узел со значением 4 в этом поддереве:

p->rchild = Delete(p->rchild, q->data);

В этом новом рекурсивном вызове мы снова получаем новый p, который теперь относится к узлу со значением 5. Мы двигаемся влево — это присваивание будет играть важную роль позже:

p->lchild = Delete(p->lchild, key);

Этот последний рекурсивный вызов имеет новый p, который ссылается на узел со значением 4 — тот, который мы искали.

На этот раз мы оказываемся в блоке if, в котором есть delete, потому что этот узел является листовым узлом. Узел освобождается, и вызывающему объекту возвращается нулевой указатель. Отсюда мы начинаем возвращаться вверх по дереву.

Таким образом, на один уровень выше, в узле со значением 5, мы получаем возвращаемое значение из рекурсивного вызова (который является нулевым указателем) и присваиваем его:

p->lchild = Delete(p->lchild, key);

Это важное назначение отделит повторяющийся узел (со значением 4) от дерева. Вы можете видеть, что если бы это присваивание не было выполнено, то все равно была бы ссылка на этот узел с повторяющимся значением, даже если оно указывает на освобожденную память.

Дерево теперь в своей окончательной форме:

                 7
                / \
               4   8
              / \   \
             1   5   9
            /     \ 
           0       6

Откат все еще будет продолжаться, возвращаясь к корню. Также выполняются присваивания некоторым дочерним указателям, но они не изменят дерево, так как во всех этих случаях мы возвращали return p;, которое было исходным значением дочернего указателя вызывающего объекта.

Ошибка

Как упоминалось в комментариях, в коде есть ошибка. При удалении листового узла не проверяется, действительно ли этот узел имеет удаляемое значение. И поэтому, если вы вызовете этот метод со значением, которого нет в дереве, вы в конечном итоге удалите конечный узел с другим значением. В приведенном выше примере дерева: если вы вызовете Delete(root, 10), узел со значением 9 будет удален.

Чтобы исправить эту ошибку, переместите следующий блок if:

if (p->lchild == nullptr && p->rchild == nullptr){

... внутри внешнего блока else в качестве первого оператора.