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