Дерево поиска
В информатике дерево поиска — это древовидная структура данных, используемая для поиска определенных ключей в наборе. Чтобы дерево функционировало как дерево поиска, ключ для каждого узла должен быть больше, чем любые ключи в поддеревьях слева, и меньше, чем любые ключи в поддеревьях справа. [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). «Двоичное дерево поиска»
| Базы данных органов управления : Национальные |
|---|
