21
правка
Изменения
Нет описания правки
[[Файл:Binary_search_tree.svg.png|right|200px|thumb|Бинарное дерево поиска из 9 элементов]]'''Бинарное дерево поиска (англ. binary search tree, BST)''' - структура данных для работы с динамическими множествами.
Бинарное дерево поиска должно обладать следующим свойством: Если <tex>x </tex> - узел бинарного дерева с ключом <tex>k</tex>, то все узлы в левом поддереве должны иметь ключи, меньшие или равные <tex>k</tex>, а в правом поддереве большие <tex>k</tex>.
== Операции в бинарном дереве поиска ==
=== обход дерева поиска ===
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой.
Tree_search(node x, key k)
if (x == null or k == x.key) return x; if (k < x.key) return Tree_search(x.left, k);
else
return Tree_search(x.right, k);
Приведенная выше функция принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.
=== Поиск минимума и максимума ===
Tree_min(root x)
while (x.left != null)
x = x.left; return x;
Tree_max(root x)
while (x.right != null)
x = x.right; return x;
Данные функции принимают корень дерева, и возвращают минимальный(максимальный) элемент в дереве. Обе процедуры выполняются за время <tex>O(h)</tex>.
=== Поиск следующего и предыдущего элемента ===
Tree_next(root x)
if (x.right != null)
return Tree_min(x.right);
y = x.parent;
while(y != null and x == y.right)
Tree_prev(root x)
if (x.left != null)
return Tree_max(x.left);
y = x.parent;
while(y != null and x == y.left)
y = y.parent;
return y;
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя. Обе операции выполняются за время <tex>O(h)</tex>.
=== Вставка ===
Операция вставки работает аналогично поиску элемента, только при обнаружении нулевого указателя нужно подвесить на него вставляемый элемент. Приведем итеративную реализацию этого алгоритма.
