Дерево поиска
В информатике дерево поиска — это древовидная структура данных, используемая для поиска определенных ключей в наборе. Чтобы дерево функционировало как дерево поиска, ключ для каждого узла должен быть больше, чем любые ключи в поддеревьях слева, и меньше, чем любые ключи в поддеревьях справа. [1]
Преимущество деревьев поиска заключается в эффективном времени поиска при условии, что дерево достаточно сбалансировано, то есть листья на обоих концах имеют сопоставимую глубину. Существуют различные структуры данных дерева поиска, некоторые из которых также позволяют эффективно вставлять и удалять элементы, которые затем должны поддерживать баланс дерева.
Деревья поиска часто используются для реализации ассоциативного массива . Алгоритм дерева поиска использует ключ из пары ключ-значение для поиска местоположения, а затем приложение сохраняет всю пару ключ-значение в этом конкретном месте.
Виды деревьев
[ редактировать ]
Бинарное дерево поиска
[ редактировать ]Двоичное дерево поиска — это структура данных на основе узлов, в которой каждый узел содержит ключ и два поддерева: левое и правое. Для всех узлов ключ левого поддерева должен быть меньше ключа узла, а ключ правого поддерева должен быть больше ключа узла. Все эти поддеревья должны квалифицироваться как двоичные деревья поиска.
Наихудшая временная сложность поиска в бинарном дереве поиска — это высота дерева , которая может составлять всего O(log n) для дерева с n элементами.
B-дерево
[ редактировать ]B-деревья являются обобщением бинарных деревьев поиска, поскольку они могут иметь переменное количество поддеревьев в каждом узле. Хотя дочерние узлы имеют заранее определенный диапазон, они не обязательно будут заполнены данными, а это означает, что B-деревья потенциально могут тратить некоторое пространство. Преимущество состоит в том, что B-деревья не нужно перебалансировать так часто, как другие самобалансирующиеся деревья .
Благодаря переменному диапазону длины узлов B-деревья оптимизированы для систем, считывающих большие блоки данных, они также часто используются в базах данных.
Временная сложность поиска в B-дереве равна O(log n).
(a,b)-дерево
[ редактировать ](a,b)-дерево — это дерево поиска, все листья которого имеют одинаковую глубину. Каждый узел имеет как минимум a дочерних узлов и не более b дочерних узлов, а корень имеет как минимум 2 дочерних узла и не более b дочерних узлов.
a и b можно определить по следующей формуле: [2]
Временная сложность поиска (a,b)-дерева равна O(log n).
Тернарное дерево поиска
[ редактировать ]Тернарное дерево поиска — это тип дерева , которое может иметь 3 узла: младшего дочернего элемента, равного дочернего элемента и старшего дочернего элемента. В каждом узле хранится один символ, а само дерево упорядочивается так же, как дерево двоичного поиска, за исключением возможного третьего узла.
Поиск в троичном дереве поиска предполагает передачу строки , чтобы проверить, содержит ли ее какой-либо путь.
Временная сложность поиска в сбалансированном троичном дереве поиска равна O(log n).
Алгоритмы поиска
[ редактировать ]Поиск определенного ключа
[ редактировать ]Предполагая, что дерево упорядочено, мы можем взять ключ и попытаться найти его внутри дерева. Следующие алгоритмы обобщены для бинарных деревьев поиска, но ту же идею можно применить и к деревьям других форматов.
Рекурсивный
[ редактировать ]search-recursive(key, node) if node is NULL return EMPTY_TREE if key < node.key return search-recursive(key, node.left) else if key > node.key return search-recursive(key, node.right) else return node
Итеративный
[ редактировать ]searchIterative(key, node) currentNode := node while currentNode is not NULL if currentNode.key = key return currentNode else if currentNode.key > key currentNode := currentNode.left else currentNode := currentNode.right
Ищем мин и макс
[ редактировать ]В отсортированном дереве минимум находится в крайнем левом узле, а максимум — в крайнем правом узле. [3]
Минимум
[ редактировать ]findMinimum(node) if node is NULL return EMPTY_TREE min := node while min.left is not NULL min := min.left return min.key
Максимум
[ редактировать ]findMaximum(node) if node is NULL return EMPTY_TREE max := node while max.right is not NULL max := max.right return max.key
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Блэк, Пол и Питерс, Вреда (2005). «дерево поиска» . Словарь алгоритмов и структур данных
- ^ Тоал, Рэй. «(а, б) Деревья»
- ^ Гильдеа, Дэн (2004). «Двоичное дерево поиска»
| Базы данных органов управления : Национальные |
|---|
