В информатике дерево поиска — это древовидная структура данных, используемая для поиска определенных ключей в наборе. Чтобы дерево функционировало как дерево поиска, ключ для каждого узла должен быть больше любых ключей в поддеревьях слева и меньше любых ключей в поддеревьях справа. [1]
Преимущество деревьев поиска заключается в их эффективном времени поиска, учитывая, что дерево разумно сбалансировано, то есть листья на обоих концах имеют сопоставимую глубину. Существуют различные структуры данных деревьев поиска, некоторые из которых также позволяют эффективно вставлять и удалять элементы, и эти операции затем должны поддерживать баланс дерева.
Деревья поиска часто используются для реализации ассоциативного массива . Алгоритм дерева поиска использует ключ из пары ключ-значение для поиска местоположения, а затем приложение сохраняет всю пару ключ-значение в этом конкретном месте.
Двоичное дерево поиска — это структура данных на основе узлов, где каждый узел содержит ключ и два поддерева, левое и правое. Для всех узлов ключ левого поддерева должен быть меньше ключа узла, а ключ правого поддерева должен быть больше ключа узла. Все эти поддеревья должны подпадать под определение бинарных деревьев поиска.
В худшем случае временная сложность поиска в бинарном дереве поиска равна высоте дерева , которая может быть всего лишь O(log n) для дерева с n элементами.
B-деревья являются обобщениями двоичных деревьев поиска, поскольку они могут иметь переменное количество поддеревьев в каждом узле. Хотя дочерние узлы имеют предопределенный диапазон, они не обязательно будут заполнены данными, что означает, что B-деревья могут потенциально тратить некоторое пространство впустую. Преимущество в том, что B-деревья не нужно перебалансировать так часто, как другие самобалансирующиеся деревья .
Благодаря переменному диапазону длины узлов B-деревья оптимизированы для систем, считывающих большие блоки данных; они также широко используются в базах данных.
Временная сложность поиска в B-дереве составляет O(log n).
(A,b)-дерево — это дерево поиска, все листья которого имеют одинаковую глубину. Каждый узел имеет не менее a и не более b потомков, в то время как корень имеет не менее 2 и не более b потомков.
a и b можно определить по следующей формуле: [2]
Временная сложность поиска в (a,b)-дереве составляет O(log n).
Троичное дерево поиска — это тип дерева , которое может иметь 3 узла: младший дочерний элемент, равный дочерний элемент и старший дочерний элемент. Каждый узел хранит один символ, а само дерево упорядочено так же, как и бинарное дерево поиска, за исключением возможного третьего узла.
Поиск в троичном дереве поиска подразумевает передачу строки для проверки того, содержит ли ее какой-либо путь.
Временная сложность поиска в сбалансированном троичном дереве поиска составляет O(log n).
Предполагая, что дерево упорядочено, мы можем взять ключ и попытаться найти его в дереве. Следующие алгоритмы обобщены для бинарных деревьев поиска, но ту же идею можно применить к деревьям других форматов.
search-recursive(ключ, узел) если узел равен NULL вернуть EMPTY_TREE если ключ < node.key возврат поиска-рекурсивный(ключ, узел.левый) иначе если ключ > узел.ключ возврат поиска-рекурсивный(ключ, узел.правый) иначе вернуть узел
searchIterative(ключ, узел) текущийУзел := узел пока currentNode не равен NULL, если currentNode.key = key, вернуть currentNode, иначе, если currentNode.key > key текущийУзел := текущийУзел.левый еще текущийУзел := текущийУзел.право
В отсортированном дереве минимум находится в самом левом узле, а максимум — в самом правом узле. [3]
findMinimum(node) если node равен NULL вернуть EMPTY_TREE мин := узел пока min.left не равен NULL мин := мин.осталось возврат мин.ключа
findMaximum(node) если node равен NULL вернуть EMPTY_TREE макс := узел пока max.right не равен NULL макс := макс.право вернуть макс.ключ
