188
правок
Изменения
м
англоязычные термины, тире
[[Файл:Binary_search_tree.svg.png|right|300px|thumb|Бинарное дерево поиска из 9 элементов]]'''Бинарное дерево поиска ''' (англ. ''binary search tree, BST)''' ) {{--- }} структура данных для работы с [[Упорядоченное множество|упорядоченными множествами]].Бинарное дерево поиска обладает следующим свойством: если <tex>x</tex> {{--- }} узел бинарного дерева с ключом <tex>k</tex>, то все узлы в левом поддереве должны иметь ключи, меньшие <tex>k</tex>, а в правом поддереве большие <tex>k</tex>.
== Операции в бинарном дереве поиска ==
=== Обход дерева поиска ===
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:
* inorderTraversal {{- --}} обход узлов в отсортированном порядке* prefixTraversal {{--- }} обход узлов в порядке: вершина, левое поддерево, правое поддерево* postfixTraversal {{--- }} обход узлов в порядке: левое поддерево, правое поддерево, вершина
'''inorderTraversal'''(Node x)
'''if''' x != null
=== Поиск элемента ===
[[Файл:Bst search.png|thumb|318px|Поиск элемента 4]]
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> {{- --}} высота дерева.
Node '''search'''(Node x, key k)
'''if''' x == null '''or''' k == x.key
