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

Что такое двоичное дерево поиска?

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

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

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

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

Существует основной узел или родительский уровень 11. Под ним находятся левые и правые узлы/ветви со своими значениями ключей.
Правое поддерево имеет ключевые значения, превышающие значения родительского узла.
Левое поддерево имеет значения, чем родительский узел

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

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

Типы двоичных деревьев

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

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

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

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

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

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

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

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

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

Поиск Operaпроизводство

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

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

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

search(element, root)
     if !root
    	return -1
     if root.value == element
    	return 1
     if root.value < element
    	search(element, root.right)
      else
    	search(element, root.left)

Вставить Operaпроизводство

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

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

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

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
    	y = x
    if x.value < element.value
        x = x.right
    else
        x = x.left
    if y.value < element
    	y.right = element
    else
    	y.left = element

Удалить Operaных

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

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

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

Это первый случай удаления, при котором вы удаляете узел, не имеющий дочерних элементов. Как видно на схеме, у 19, 10 и 5 детей нет. Но мы удалим 19.
Удалите значение 19 и удалите ссылку из узла.
Посмотреть новую структуру БСТ без 19

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

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

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

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

delete (value, root):
    Node x = root
    Node y = NULL
# searching the node
    while x:
    	y = x
    if x.value < value
        x = x.right
    else if x.value > value
        x = x.left
    else if value == x
        break
# if the node is not null, then replace it with successor
    if y.left or y.right:
    	newNode = GetInOrderSuccessor(y)
    	root.value = newNode.value
# After copying the value of successor to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Важные термины

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

Резюме

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