Дерево поиска, наивная реализация

Бинарное дерево поиска из 9 элементов

Бинарное дерево поиска (англ. binary search tree, BST) - структура данных для работы с динамическими множествами.

Бинарное дерево поиска должно обладать следующим свойством: Если x - узел бинарного дерева с ключом k, то все узлы в левом поддереве должны иметь ключи, меньшие k, а в правом поддереве большие k.

Операции в бинарном дереве поиска

обход дерева поиска

Имеется простой алгоритм вывода всех ключей бинарного дерева поиска в отсортированном порядке.

Tree_walk(node x)
   if(x != null)
      Tree_walk(x.left);
      print(x.key);
      Tree_walt(x.right);

Данный алгоритм выполняет обход за время [math]O(n)[/math], поскольку процедура вызывается ровно два раза для каждого узла дерева. Корректность данного алгоритма следует из свойств бинарного дерева поиска.

поиск элемента

поиск минимума и максимума поиск следующего и предыдущего элемента вставка удаление

Литература

1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4