Есть бинарное дерево, надо удалить из него элемент. Нашел вариант - удаляем элемент а на его место ставим либо самый правый элемент его левого поддерева либо самый левый его правого поддерева. Вопрос: как это лучше всего организовать? Логично, что надо у замещающего элемента дописать указатели на поддеревья а у его владельца заменить указатель на него на NULL, причем у владельца удаляемого элемента заменить указатель на замещающий элемент. Если делать все в лоб, то нужны 2 указателя на поддеревья, указатели на родителей и указатели на сами элементы. Есть ли некий правильный способ удаления без этого гемора? Возможно более оптимизированный. Просьба посмотреть мой код строка 164 - функция не линкуется, а вроде нормально написано.
Ответ
В случае бинарного дерева поиска рекомендую посмотреть корректный алгоритм в Кормене ("Алгоритмы. Построение и анализ" - страница 326), либо в более простом и наглядном варианте здесь. В обоих случаях используется классическая структура данных для хранения BST, в которой элемент представлен кортежем (parent, left, right, data) В случае же обычного бинарного дерева нетривиальна только ситуация, когда у удаляемого элемента ссылки left и right - не null. В этой ситуации необходимо совершить обход по дереву в сторону left или right, найти первый возможный лист в дереве и заменить удаляемый элемент на данный лист. Для оптимизации такой операции возможно хранить в каждом узле дерева дополнительное поле leaf, которое будет указывать на такой возможный лист, чтобы избежать прохода по ветке дерева в случае удаления элемента. Хотя, как мне кажется, интерес в такой оптимизации является сугубо теоретическим.
Комментариев нет:
Отправить комментарий