В моей последней статье я объяснил стеки и очереди. В этом выпуске я сейчас углублюсь в более сложные структуры данных, но прежде чем определить, что такое двоичное дерево поиска. Давайте определим, что такое простое Дерево в мире информатики.
Дерево: структура данных, состоящая из узлов в отношениях родитель-потомок.
Слева — визуальное представление простого Дерева. Вы можете думать о деревьях как о настоящем дереве, но оно перевернуто.
Есть несколько терминов, с которыми вы должны быть знакомы при работе с этими типами структур данных.
Корень. Верхний узел в дереве, в данном примере это 2.
Дочерний элемент: узел, напрямую соединенный с другим узлом при удалении от корня. Как видно из примера, 7 является потомком 2.
Родитель: обратная сторона дочернего элемента, в данном примере 2 является родителем 7.
Родственные узлы. Группа узлов с одним родителем. Таким образом, в этом случае 2, 10 и 6 называются братьями и сестрами.
Листок. Узел без дочерних элементов. В случае примера 5, 11 и 4 называются листьями дерева.
Граница. Соединение между одним узлом и другим.
Деревья имеют множество применений, и мы почти не замечаем этого. Примеры включают Дерево HTML DOM, папки в любой используемой операционной системе, а также Абстрактное дерево синтаксиса, которое является просто способом представления синтаксиса языка программирования. в виде «дерева». Это дерево представляет все конструкции языка и его последующие правила.
Двоичные деревья поиска
Бинарное дерево поиска (BST) — это особый вариант деревьев. У них есть особые правила, которые делают их уникальными. Они перечислены ниже.
1) Каждый узел в дереве должен иметь не более 2 дочерних элементов.
2) Каждый узел слева от родительского узла всегда меньше родительского узла.
3) Каждый узел справа от родительский узел всегда больше родительского узла,
Как видно из примера слева, в левой части корня дерева (50) каждое значение меньше корня, а в правой части каждое значение больше чем корень. Правила соблюдаются, даже когда вы проходите вниз по BST, как вы можете видеть слева от 30 значение равно 20, что явно меньше 30, а справа от 30 значение равно 40.
Вы можете реализовать BST, используя реализацию связанного списка, подобно тому, как я реализовал стеки и очереди в последнем выпуске.
Узел в BST как 3 свойства: право, лево и значение. Вправо и влево — это просто указатели, которые делают то, что говорят. Они указывают текущий узел на узлы слева и справа. Значение — это просто данные, которые содержит узел. Это может быть строка, целое число и т. д., но для простоты мы будем визуализировать только целые числа.
В BST есть два важных метода: insert() и find(). Вставка позволяет вставить узел в BST, проверяя, больше или меньше вставляемый узел, чем корневой узел. Мы используем эту стратегию при обходе дерева, чтобы вставить его в нужное место. Скриншот кода выше с псевдокодом объясняет алгоритм того, как мы проходим вниз по BST, чтобы вставить узел в нужное место.
Метод find() похож на метод insert() с одним существенным отличием: мы не вставляем новый узел в дерево, а находим уже существующий узел и возвращаем его. Оба метода в BST, по сути, зацикливаются (проходят) через BST до тех пор, пока не будет выполнено условие, и мы не вернем то, что хотим.
Временная сложность
Наилучший случай как для вставки, так и для метода поиска — O(log n). Это связано с расположением данных в BST.
Вернемся к предыдущему примеру. Если бы мы вставили число 10 в это дерево, мы могли бы полностью проигнорировать правую часть дерева, алгоритм будет знать, что нужно использовать только левую часть дерева для вставки узла. Из-за этого, если бы мы увеличили размер этого BST, добавив дочерние элементы к листьям и выполнив ту же операцию, мы действительно увеличили бы количество шагов для перехода от родителя к дочернему элементу только на 1. Это объяснение то же самое для метода find().
