Удаление узла бинарного дерева

#cpp #алгоритм

Есть бинарное дерево, надо удалить из него элемент.
Нашел вариант - удаляем элемент а на его место ставим либо самый правый элемент его
левого поддерева либо самый левый его правого поддерева.
Вопрос: как это лучше всего организовать?
Логично, что надо у замещающего элемента дописать указатели на поддеревья а у его
владельца заменить указатель на него на NULL, причем у владельца удаляемого элемента
заменить указатель на замещающий элемент.
Если делать все в лоб, то нужны 2 указателя на поддеревья, указатели на родителей
и указатели на сами элементы.
Есть ли некий правильный способ удаления без этого гемора? Возможно более оптимизированный.
Просьба посмотреть мой код строка 164 - функция не линкуется, а вроде нормально написано.    

Ответы

Ответ 1

В случае бинарного дерева поиска рекомендую посмотреть корректный алгоритм в Кормене
("Алгоритмы. Построение и анализ" - страница 326), либо в более простом и наглядном
варианте здесь.
В обоих случаях используется классическая структура данных для хранения BST, в которой
элемент представлен кортежем (parent, left, right, data).

В случае же обычного бинарного дерева нетривиальна только ситуация, когда у удаляемого
элемента ссылки left и right - не null. В этой ситуации необходимо совершить обход
по дереву в сторону left или right, найти первый возможный лист в дереве и заменить
удаляемый элемент на данный лист.
Для оптимизации такой операции возможно хранить в каждом узле дерева дополнительное
поле leaf, которое будет указывать на такой возможный лист, чтобы избежать прохода
по ветке дерева в случае удаления элемента. Хотя, как мне кажется, интерес в такой
оптимизации является сугубо теоретическим.