Как удалить узел от дерева BST с 2 детьми?

Question

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

Я нашел 4 алгоритма, чтобы удалить узел с 2 детьми из двоичного поиска:
1) Найдите наименьший узел с правого подпада и замените его узлом, который мы хотим удалить.
2) Найдите самый большой узел из левой подпэри и замените его узлом, который мы хотим удалить.
3) Найдите самый глубокий левый узел с правого подпада и замените его узлом, который мы хотим удалить.
4) Найдите самый глубокий правый узел из левого подпэре и замените его узлом, который мы хотим удалить.

Видимо, ни один из этих алгоритмов не работает для следующего случая использования (скорее всего, потому что я не хватаю или не понимаю что-то). Корпус использования - удалить элемент 5 от следующего дерева:

Для первого алгоритма мы выбрали бы элемент 6 и потерял бы правый подп. Для второго алгоритма мы выбрали бы элемент 4 и потеряли бы левый подп. Для 3-го алгоритма мы выбрали бы элемент 7, и который нарушит правила BST. Для 4-го алгоритма мы выбирали бы элемент 3, который также нарушит правила BST.

Что такое правильный алгоритм для такого случая использования?

Answer 1

Вы правы, в BST обычно случай, когда узел имеет два детей, сводится к корпусу, когда узел имеет один ребенок.

Рассмотрим узел с двумя детьми. Смейте этот узел своим предшественником в BST (это самый правый узел в левом поддереве) или --тотально симметрично - своп с преемником (самый левый узел в правом поддельноме).

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

В случае, если узел имеет один ребенок, мы вынимаем узел и замените его под поддерево. Мы снова получим BST.

В вашем примере мы хотим удалить 5 и поменять его со своим предшественником 4. Теперь 4 находится в корне, а 5 оставил ребенка 3. Наконец-то мы удаляем 5 и поставьте его ребенку на свое место. Сейчас 3 - это правильный ребенок из 2.

PS. Этот метод иногда называют «удалением, копируя», потому что значения скопированы с одного узла в другое. Некоторые не одобряют этот процесс по двум причинам. Первое копирование может быть дорогой операцией, а вторые ссылки теряются (если другая таблица данных указывает на узел с определенным значением). Вместо этого только меняет указатели.