21
правка
Изменения
Нет описания правки
return Tree_search(x.right, k)
Приведенная выше функция принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.
=== поиск минимума и максимума===Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям left от корня дерева, пока не встретится значение hull. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям. 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>.=== поиск следующего и предыдущего элемента====== вставка====== удаление===
== Литература ==
1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
