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

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

Как реализовать функцию удаления узла из дерева двоичного поиска? Ниже моя текущая функция:

А вот и remove у меня есть функция, которая находит значение, которое будет удалено:

Сейчас я чувствую, что я очень близок, но когда я выхожу, чтобы вывести содержимое двоичного дерева, программа вылетает. Я пытаюсь использовать подход, при котором, если у узла есть два дочерних элемента, я определяю преемника по порядку, меняю значения узлов преемника по порядку и «удаляемого» узла, а затем удаляю преемника по порядку , Без корректировки remove функции, какую часть информации мне не хватает, чтобы сделать makeDeletion Функция работы, как описано?

РЕДАКТИРОВАТЬ: в makeDeletion Функция, которую я по ошибке написал два if заявления подряд. Второй if заявление должно быть else if заявление.

Решение

В makeDeletion , если tree это лист (оба left а также right являются NULL ), вы удаляете листовой узел и не устанавливаете tree = nullptr , Это оставляет в вашем дереве свисающую ссылку на память, которая была освобождена. Кроме того, вы затем разыменовываете (теперь удаленный) узел в следующем if , Любой из них может привести к вашей аварии.

Двоичное дерево поиска. Итеративная реализация.

Д воичные деревья – это структуры данных, состоящие из узлов, которые хранят значение, а также ссылку на свою левую и правую ветвь. Каждая ветвь, в свою очередь, является деревом. Узел, который находится в самой вершине дерева принято называть корнем (root), узлы, находящиеся в самом низу дерева и не имеющие потомков называют листьями (leaves). Ветви узла называют потомками (descendants). По отношению к своим потомкам узел является родителем (parent) или предком (ancestor). Также, развивая аналогию, имеются сестринские узлы (siblings – родные братья или сёстры) – узлы с общим родителем. Аналогично, у узла могут быть дяди (uncle nodes) и дедушки и бабушки ( grandparent nodes). Такие названия помогают понимать различные алгоритмы.

Двоичные деревья одна из самых простых структур (по сравнению, например, с другими деревьями). Они обычно реализуют самый базовый и самый естественный способ классификации элементов – делят их по определённому признаку, размещая одну группу в левом поддереве, а другую группу в правом. В поддеревьях рекурсивно поддерживается такой же порядок, за счёт чего узлы дерева упорядочиваются.

Двоичное дерево поиска (далее ДДП) – это несбалансированное двоичное дерево, в котором элементы БОЛЬШЕ корневого размещаются справа, а элементы, которые МЕНЬШЕ размещаются слева.

Читайте также:  Тест на дабл клик

Такое размещение – слева меньше, справа больше – не обязательно, можно располагать элементы, которые меньше, справа. Отношение БОЛЬШЕ и МЕНЬШЕ – это не обязательно естественная сортировка по величине, это некоторая бинарная операция, которая позволяет разбить элементы на две группы.

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

ЗАМЕЧАНИЕ: мы рассматриваем случай, когда в дереве все значения разные и не равны NULL. Деревья с повторяющимися узлами рассмотрим позднее.

Обычно в качестве типа данных мы используем void* и далее передаём функции сравнения через указатели. В этот раз будем использовать пользовательский тип и макросы.

Сначала, как обычно, напишем функцию, которая создаёт новый узел. Она принимает в качестве аргументов значение и указатель на своего родителя. Корневой элемент не имеет родителя, значение указателя parent равно NULL.

Разберёмся со вставкой. Возможны следующие ситуации

  • 1) Дерево пустое. В этом случае новый узел становится корнем ДДП.
  • 2) Новое значение меньше корневого. В этом случае значение должно быть вставлено слева. Если слева уже стоит элемент, то повторяем эту же операцию, только в качестве корневого узла рассматриваем левый узел. Если слева нет элемента, то добавляем новый узел.
  • 3) Новое значение больше корневого. В этом случае новое значение должно быть вставлено справа. Если справа уже стоит элемент, то повторяем операцию, только в качестве корневого рассматриваем правый узел. Если справа узла нет, то вставляем новый узел.

Пусть нам необходимо поместить в ДДП следующие значения

10 7 9 12 6 14 11 3 4

Первое значение становится корнем.

Второе значение меньше десяти, так что оно помещается слева.

Заметки по программированию на C# .NET, Python, Java и Android программированию

Бинарное дерево — двоичное дерево поиска. Основные операции с бинарными деревьями (C#, Java)

Что такое бинарное дерево

Бинарное дерево представляет собой иерархическую структуру данных, в которой каждый узел имеет не более двух дочерних узлов. Как правило, первый называется родительским узлом или корнем дерева (root), а дочерние узлы называются левым и правым наследниками.

Читайте также:  Геймпад клавиатура для пк

Бинарное дерево либо является пустым, либо состоит из данных и двух поддеревьев, каждое из которых может быть пустым. Каждое поддерево в свою очередь тоже является деревом. Узлы без наследников принято называть листьями.

Для такого дерева должны выполняться следующие условия:

  1. Левое и правое поддерево так же являются бинарными деревьями;
  2. У всех узлов левого поддерева произвольного узла x значения ключей данных меньше значения ключа данных самого узла x ;
  3. У всех узлов правого поддерева произвольного узла x значения ключей данных больше либо равны значению ключа данных самого узла x .

Основные операции с бинарным деревом

Основными операциями с бинарными деревьями являются добавление элемента в дерево, удаление элемента и поиск элемента в дереве. Сложность каждой из этих операций O(log,n) в лучшем случае, и O(n) в худшем. Зависит от сбалансированности дерева.

Пример сбалансированного бинарного дерева (лучший случай):

Пример несбалансированного бинарного дерева (худший случай):Добавление элемента в дерево

При добавлении элемента x в дерево проверяем значение текущего узла.

  • Если значение добавляемого элемента x меньше значения текущего узла, спускаемся к левому поддереву. Если его не существует, то создаем его и присваиваем значение x . Если существует, то обозначим левое поддерево как текущий узел и повторим сначала.
  • Если значение добавляемого элемента x больше или равно значению текущего узла, спускаемся к правому поддереву. Если его не существует, то создаем его и присваиваем значение x . Если существует, то обозначим правое поддерево как текущий узел и повторим сначала.

Пример добавления элемента в двоичное дерево

Создадим бинарное дерево с корневым элементом 33 и добавим в него элементы в следующей последовательности: 5, 35, 1, 20, 99, 17, 18, 19, 31, 4. Получим бинарное дерево такого вида:

Поиск элемента в бинарном дереве

Поиск начинаем с родительского элемента. Допустим, мы ищем значение 18 (обозначим его за x ). Алгоритм поиска будет иметь следующий вид:

  1. x — спускаемся в левое поддерево;
  2. x>5 — спускаемся в правое поддерево;
  3. x — спускаемся в левое поддерево;
  4. x>17 — спускаемся в правое поддерево;
  5. x=18 — мы нашли элемент.

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

Удаление элемента из бинарного дерева

Удаление листьев

Если удаляемый элемент является листом, то просто удаляем у его родителя ссылку на этот элемент (например на значение 31). Удалим его.

Читайте также:  Почему при загрузке игры выключается компьютер

Удаление узла, имеющего левое поддерево, но не имеющее правого поддерева

После удаления 31 элементом, имеющим левое поддерево, но не имеющим правого поддерева является элемент 20. Удалим его из дерева:

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

После удаления значений 31 и 20 дерево приобретает такой вид:

Удаление узла, имеющего правое поддерево, но не имеющее левого поддерева

  1. Удалим элемент 17. Присвоим его правому поддереву в качестве родителя элемент 5.
  2. Элементу 5 укажем, что его правым поддеревом теперь является элемент 18.

Получим следующую картину:

Удаляем узел, имеющий поддеревья с обеих сторон

Первый случай

Правое поддерево не имеет потомка.

Чтобы иметь возможность рассмотреть этот случай, добавим элемент 34 в дерево:Удалим элемент 35. Для этого:

  1. Правому поддереву (99) присвоим в качестве родителя элемент 33;
  2. Ему же в качестве левого поддерева присваиваем элемент 34;
  3. Элементу 34 указываем нового родителя — 99;
  4. Родителю удаляемого элемента (33) указываем, что его правым поддерево теперь является элемент 99.

Получим такое дерево:

Второй случай

Правое поддерево имеет своих потомков.

Удаляем элемент 5. Первым потомком (одновременно самым левым — минимальным в его поддереве) элемента 5 является элемент 18:

  1. Элементу 18 в качестве левого узла присвоим элемент 1;
  2. Элементу 1 присвоим 18 как родителя;
  3. Элементу 33 (родителю удаляемого элемента) укажем в качестве левого дочернего узла элемент 18;
  4. Элементу 18 указываем в качестве родителя элемент 33 (родитель удаляемого элемента).

Дерево приобретает такой вид:

Если минимальный левый элемент имеет правых потомков и при это не является первым потомком удаляемого элемента, то его правый потомок присваивается родителю минимального элемента правого поддерева.

В своем коде я использовал нерекурсивный механизм удаления.

Существуют и другие механизмы удаления. Визуализировать свое дерево вы можете на ресурсе usfca.edu. Вы заметите, что алгоритм удаления там отличается от описанного выше.

Код класса дерева на Java в моем исполнении имеет следующий вид:

Поработать с классом можно следующим образом:

Получим такой вывод:

К слову, на Java такой код особого смысла писать нет, т.к. там существуют классы TreeSet и TreeMap, представляющие собой деревья.

На C# код класса бинарного дерева может иметь такой вид:

Код примерно такой же, только для C# он будет гораздо полезнее.

Ссылка на основную публикацию
Топ лучших видеокарт для игр
Видеокарты крайне быстро улучшаются, практически каждые полгода выходит видеоадаптер, значительно превосходящий предшественника. Активный прогресс обусловлен быстрым увеличением системных требований компьютерных...
Телефон леново включается но не запускается
Бывает, что пользователь включает свой смартфон, процесс доходит до заставки (логотипа) и дальше не грузится. Сразу начинается паника, ведь телефон...
Телефон леново инструкция для чайников
Большинство из нас чувствует себя неуверенно, когда приходится знакомиться с новой операционной системой. И несмотря на то, что Андроид сегодня...
Топ приложений для запоминания слов
Топ-8 приложений, где запоминать английские слова Приложения для изучения английских слов помогают быстро и эффективно пополнять словарный запас. Без работы...
Adblock detector