3

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

Просьба посмотреть мой код строка 164 - функция не линкуется, а вроде нормально написано.

1
  • Сделайте "в лоб". А там может увидите способы оптимизации. 17 ноя 2011 в 13:39

1 ответ 1

8

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

В обоих случаях используется классическая структура данных для хранения BST, в которой элемент представлен кортежем (parent, left, right, data).


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

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

1
  • Шикарный алгоритм, благодарю. Я бы долго до него допирал)) 17 ноя 2011 в 15:35

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.