Дерево поиска

Дерево поиска — это структура данных дерева, используемая для нахождения конкретных ключей в наборе. Чтобы дерево функционировало как дерево поиска, ключ каждого узла должен быть больше всех ключей в левых поддеревьях и меньше всех ключей в правых поддеревьях^[1].

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

Деревья поиска часто используются для реализации ассоциативного массива. Алгоритм дерева поиска использует ключ из пары «ключ-значение» для определения местоположения, а затем приложение сохраняет всю пару «ключ-значение» в этом конкретном месте.

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

В худшем случаевременна́я сложность поиска в двоичном дереве равна высоте дерева, которая может составлять всего O(log n) для дерева с n элементами.

B-деревья являются обобщением двоичных деревьев поиска, поскольку каждый узел дерева может иметь различное число поддеревьев. Хотя количество (прямых) потомков^[a] предопределено, они не обязательно будут заполнены данными, что означает, что B-деревья могут потенциально тратить некоторое пространство. Преимущество заключается в том, что B-деревья не требуют такой частой перебалансировки, как другие сбалансированные деревья.

Благодаря переменному диапазону длины узлов, B-деревья оптимизированы для систем, которые считывают большие блоки данных, и часто используются в базах данных.

Временна́я сложность поиска в B-дереве составляет O(log n).

(a,b)-дерево — это дерево поиска, у которого все листья находятся на одной глубине. Каждый узел имеет по меньшей мере a потомка и не больше b потомков, в то время как корень дерева имеет не менее 2 и не более b потомков.

Значения a и b должны удовлетворять следующей формуле^[2]:

${\displaystyle 2\leqslant a\leqslant {\frac {(b+1)}{2}}}$

Временна́я сложность поиска в (a,b)-дереве составляет O(log n).

Троичное дерево поиска — это тип дерева, которое может иметь 3 потомков узла — меньший потомок, равный потомок и бо́льший потомок. Каждый узел хранит один символ и дерево само упорядочено так же, как и двоичное дерево поиска, за исключением третьего потомка.

Поиск в троичном дереве поиска включает передачу строки для проверки того, содержится ли она на каком-либо пути.

Временна́я сложность в сбалансированном троичном дереве поиска составляет O(log n).

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

search-recursive(key, node) if node is NULLreturnEMPTY_TREEif key < node.key return search-recursive(key, node.left) else if key > node.key return search-recursive(key, node.right) elsereturn node 

searchIterative(key, node) currentNode := node while currentNode is not NULLif currentNode.key = key return currentNode else if currentNode.key > key currentNode := currentNode.left else currentNode := currentNode.right 

В отсортированном дереве минимальное значение находится в самом левом наследнике^[b], а максимальное — в самом правом наследнике^[3].

findMinimum(node) if node is NULLreturnEMPTY_TREE min := node while min.left is not NULL min := min.left return min.key 

findMaximum(node) if node is NULLreturnEMPTY_TREE max := node while max.right is not NULL max := max.right return max.key 

• Префиксное дерево
• Двоичное дерево
• Поиск в глубину