Двоичное дерево поиска (BST) с примером

Двоичное дерево поиска — это расширенный алгоритм, используемый для анализа узла, его левой и правой ветвей, которые моделируются в виде древовидной структуры и возвращают значение. BST разработан на основе архитектуры базового алгоритма бинарного поиска; следовательно, он обеспечивает более быстрый поиск, вставку и удаление узлов. Это делает программу действительно быстрой и точной.

В этом руководстве по структуре данных вы узнаете:

• Что такое бинарное дерево поиска?
• Атрибуты бинарного дерева поиска
• Зачем нам нужно двоичное дерево поиска?
• Типы бинарных деревьев
• Как работает бинарное дерево поиска?
• Важные условия

Атрибуты бинарного дерева поиска

BST состоит из нескольких узлов и состоит из следующих атрибутов:

• Узлы дерева представлены в отношениях родитель-потомок
• Каждый родительский узел может иметь ноль дочерних узлов или максимум два подузла или поддеревья слева и справа.
• Каждое поддерево, также известное как бинарное дерево поиска, имеет подветви справа и слева от себя.
• Все узлы связаны парами ключ-значение.
• Ключи узлов, присутствующих в левом поддереве, меньше, чем ключи их родительского узла.
• Точно так же ключи узлов левого поддерева имеют меньшие значения, чем ключи их родительского узла.

1. Есть главный узел или родительский уровень 11. Под ним есть левый и правый узлы/ветви со своими значениями ключей
2. В правом поддереве значения ключей больше, чем в родительском узле.
3. Левое поддерево имеет значения, чем родительский узел

Зачем нам нужно двоичное дерево поиска?

• Двумя основными факторами, которые делают бинарное дерево поиска оптимальным решением любых реальных проблем, являются скорость и точность.
• Из-за того, что бинарный поиск имеет ветвящийся формат с отношениями родитель-потомок, алгоритм знает, в каком месте дерева нужно искать элементы. Это уменьшает количество сравнений ключ-значение, которое программа должна выполнить, чтобы найти нужный элемент.
• Кроме того, если искомый элемент больше или меньше родительского узла, узел знает, на какой стороне дерева искать. Причина в том, что левое поддерево всегда меньше родительского узла, а правое поддерево всегда имеет значения, равные родительскому узлу или превышающие его.
• BST обычно используется для реализации сложных поисков, надежной игровой логики, действий автозаполнения и графики.
• Алгоритм эффективно поддерживает такие операции, как поиск, вставка и удаление.

Типы бинарных деревьев

Три вида бинарных деревьев:

• Полное бинарное дерево: все уровни в деревьях заполнены возможными исключениями последнего уровня. Точно так же заполняются все узлы, направляющие в крайний левый угол.
• Полное двоичное дерево: все узлы имеют 2 дочерних узла, кроме листа.
• Сбалансированное или идеальное бинарное дерево: в дереве все узлы имеют двух дочерних элементов. Кроме того, существует одинаковый уровень каждого подузла.

Узнайте больше о двоичном дереве в структуре данных, если вам интересно.

Как работает бинарное дерево поиска?

Дерево всегда имеет корневой узел и дополнительные дочерние узлы, слева или справа. Алгоритм выполняет все операции, сравнивая значения с корнем и его дальнейшими дочерними узлами в левом или правом поддереве соответственно.

В зависимости от элемента, который нужно вставить, найти или удалить, после сравнения алгоритм может легко удалить левое или правое поддерево корневого узла.

BST в первую очередь предлагает следующие три типа операций для вашего использования:

• Поиск: ищет элемент в бинарном дереве.
• Insert: добавляет элемент в бинарное дерево.
• Удалить: удалить элемент из бинарного дерева.

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

Операция поиска

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

1. Искомый элемент равен 10.
2. Сравните элемент с корневым узлом 12, 10 < 12, следовательно, вы переместитесь в левое поддерево. Нет необходимости анализировать правое поддерево
3. Теперь сравните 10 с узлом 7, 10> 7, поэтому перейдите к правому поддереву.
4. Затем сравните 10 со следующим узлом, который равен 9, 10> 9, посмотрите в правом дочернем поддереве
5. 10 соответствует значению в узле, 10 = 10, возвращаем значение пользователю.

Псевдокод для поиска в BST:

поиск(элемент, корень) если !root возвращает -1 если root.value == элемент возвращает 1 если root.value < элемент поиск(элемент, корень.право) иначе поиск(элемент, корень.левый)

Вставить операцию

Это очень простая операция. Сначала вставляется корневой узел, затем следующее значение сравнивается с корневым узлом. Если значение больше корня, оно добавляется в правое поддерево, а если оно меньше корня, оно добавляется в левое поддерево.

1. Существует список из 6 элементов, которые необходимо вставить в BST в порядке слева направо.
2. Вставьте 12 в качестве корневого узла и сравните следующие значения 7 и 9 для вставки соответственно в правое и левое поддерево.
3. Сравните оставшиеся значения 19, 5 и 10 с корневым узлом 12 и расположите их соответствующим образом. 19 > 12 поместите его как правого потомка 12, 5 < 12 и 5 < 7, следовательно, поместите его как левого потомка 7. Теперь сравните 10, 10 < 12 и 10 > 7, а 10 > 9, поместите 10 как правое поддерево 9.

Псевдокод для вставки узла в BST:

вставка (элемент, корень) Узел x = корень Узел y = NULL, тогда как x: y = x, если x.value < element.value x = x.right else x = x.left, если y.value < элемент y.right = элемент иначе y.left = элемент

Удалить операции

Для удаления узла из BST есть несколько случаев, например, удаление корня или удаление конечного узла. Кроме того, после удаления корня нам нужно подумать о корневом узле.

Скажем, мы хотим удалить конечный узел, мы можем просто удалить его, но если мы хотим удалить корень, нам нужно заменить значение корня другим узлом. Возьмем следующий пример:

• Случай 1. Узел без дочерних элементов: это самая простая ситуация, вам просто нужно удалить узел, у которого нет других дочерних элементов справа или слева.
• Случай 2 — узел с одним дочерним элементом: после удаления узла просто соедините его дочерний узел с родительским узлом удаленного значения.
• Случай 3 Узел с двумя дочерними элементами: это самая сложная ситуация, и она работает по следующим двум правилам.
• 3a — В предшественнике порядка: вам нужно удалить узел с двумя дочерними элементами и заменить его наибольшим значением в левом поддереве удаленного узла.
• 3b — В порядке преемника: вам нужно удалить узел с двумя дочерними элементами и заменить его наибольшим значением в правом поддереве удаленного узла.

1. Это первый случай удаления, когда вы удаляете узел, у которого нет потомков. Как вы можете видеть на диаграмме, у 19, 10 и 5 нет детей. Но мы удалим 19.
2. Удалите значение 19 и удалите ссылку из узла.
3. Посмотреть новую структуру BST без 19

1. Это второй случай удаления, когда вы удаляете узел, у которого есть 1 дочерний элемент, как вы можете видеть на диаграмме, у 9 есть один дочерний элемент.
2. Удалите узел 9 и замените его дочерним элементом 10 и добавьте ссылку с 7 на 10.
3. Посмотреть новую структуру BST без 9

1. Здесь вы будете удалять узел 12, у которого есть два потомка.
2. Удаление узла будет происходить на основе правила предшественника по порядку, что означает, что самый большой элемент в левом поддереве из 12 заменит его.
3. Удалите узел 12 и замените его на 10, так как это наибольшее значение в левом поддереве.
4. Посмотреть новую структуру BST после удаления 12

1. 1 Удалите узел 12, у которого есть два потомка
2. 2 Удаление узла будет происходить на основе правила преемника по порядку, что означает, что самый большой элемент в правом поддереве из 12 заменит его.
3. 3 Удалите узел 12 и замените его на 19, так как это наибольшее значение в правом поддереве.
4. 4 Просмотрите новую структуру BST после удаления 12

Псевдокод для удаления узла:

delete (value, root): Node x = root Node y = NULL # поиск узла while x: y = x if x.value < value x = x.right else if x.value >value x = x.left else if value == x break # если узел не нулевой, то заменить его преемником, если y.left или y.right: newNode = GetInOrderSuccessor(y) root.value = newNode.value # После копирования значения преемника в корень #мы удаляем преемник free(newNode) else free(y)

Важные условия

• Вставить: вставляет элемент в дерево/создает дерево.
• Поиск: поиск элемента в дереве.
• Предварительный обход: обход дерева в предварительном порядке.
• Inorder Traversal: обход дерева по порядку.
• Обход в обратном порядке: обход дерева в обратном порядке.

Резюме

• BST — это алгоритм продвинутого уровня, выполняющий различные операции на основе сравнения значений узла с корневым узлом.
• Любая из точек в иерархии родитель-потомок представляет узел. По крайней мере один родительский или корневой узел присутствует все время.
• Есть левое поддерево и правое поддерево. Левое поддерево содержит значения, которые меньше корневого узла. Однако правое поддерево содержит значение, превышающее значение корневого узла.
• У каждого узла может быть ноль, один или два потомка.
• Двоичное дерево поиска облегчает основные операции, такие как поиск, вставка и удаление.
• Удалить, будучи наиболее сложным, имеет несколько случаев, например, узел без дочерних элементов, узел с одним дочерним элементом и узел с двумя дочерними элементами.
• Алгоритм используется в реальных решениях, таких как игры, данные автозаполнения и графика.

Вы могли бы:

• Жадный алгоритм на примере: что это такое, метод и подход
• Алгоритм поиска в ширину (BFS) с ПРИМЕРОМ
• Алгоритм бинарного поиска с ПРИМЕРОМ
• Деревья AVL: повороты, вставка, удаление на примере C++
• Учебник DAA в формате PDF: разработка и анализ алгоритмов