21
правка
Изменения
Нет описания правки
Tree_walt(x.right);
Данный алгоритм выполняет обход за время <tex>O(n)</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> - высота дерева.
поиск минимума и максимума
поиск следующего и предыдущего элемента
