В информатике , дерево поиска представляет собой древовидную структуру данных используется для определения местоположения конкретных ключей в наборе : . Чтобы дерево функционировало как дерево поиска, ключ для каждого узла должен быть больше, чем любые ключи в поддеревьях слева, и меньше, чем любые ключи в поддеревьях справа. [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).
Алгоритмы поиска [ править ]
Поиск определенного ключа [ править ]
Предполагая, что дерево упорядочено, мы можем взять ключ и попытаться найти его в дереве. Следующие ниже алгоритмы обобщены для деревьев двоичного поиска, но та же идея может быть применена к деревьям других форматов.
Рекурсивный [ править ]
поиск-рекурсивный (ключ, узел), если узел равен NULL, вернуть EMPTY_TREE, если ключ <node.key возврат поиск-рекурсивный (ключ, node.left) иначе, если ключ> node.key возврат поиск-рекурсивный (ключ, node.right) иначе вернуть узел
Итеративный [ править ]
searchIterative (ключ, узел) currentNode: = узел в то время как currentNode не равен NULL, если currentNode.key = key возвращает currentNode иначе, если currentNode.key> key currentNode: = currentNode.left еще currentNode: = currentNode.right
Поиск минимума и максимума [ править ]
В отсортированном дереве минимум расположен в крайнем левом узле, а максимум - в крайнем правом узле. [3]
Минимум [ править ]
findMinimum (узел), если узел равен NULL, вернуть EMPTY_TREE мин: = узел в то время как min.left не NULL мин: = мин. слева возврат мин. ключ
Максимум [ править ]
findMaximum (узел), если узел равен NULL, вернуть EMPTY_TREE макс: = узел в то время как max.right не NULL макс: = макс. справа возврат макс. ключ
См. Также [ править ]
- Trie
- Двоичное дерево
- Поиск в глубину
Ссылки [ править ]
- ^ Black, Пол и Питерс, Vreda (2005). «дерево поиска» . Словарь алгоритмов и структур данных
- ^ Toal, Рэй. "(а, б) Деревья"
- ^ Gildea, Дан (2004). «Дерево двоичного поиска»
