Дерево поиска - Search tree

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

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

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

Виды деревьев

Дерево двоичного поиска

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

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

B-дерево

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

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

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

(а, б) -дерево

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

а и б можно определить по следующей формуле:^[2]

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

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

Тернарное дерево поиска

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

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

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

Алгоритмы поиска

Поиск определенного ключа

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

Рекурсивный

поисково-рекурсивный (ключ, узел) если узел НОЛЬ        возвращаться EMPTY_TREE    если key иначе если key> node.key возврат поиск-рекурсивный (ключ, node.right) еще        возвращаться узел

Итеративный

searchIterative (ключ, узел) currentNode: = узел пока currentNode не является НОЛЬ        если currentNode.key = ключ возвращаться currentNode иначе если currentNode.key> ключ currentNode: = currentNode.left еще            currentNode: = currentNode.right

Поиск минимума и максимума

В отсортированном дереве минимум расположен в крайнем левом узле, а максимум - в крайнем правом узле.^[3]

Минимум

findMinimum (узел) если узел НОЛЬ        возвращаться EMPTY_TREE    мин: = узел пока мин. слева не НОЛЬ        мин: = мин. слева возвращаться мин. ключ

Максимум

findMaximum (узел) если узел НОЛЬ        возвращаться EMPTY_TREE    макс: = узел пока макс. справа нет НОЛЬ        макс: = макс. справа возвращаться макс. ключ