Дерево поиска, наивная реализация — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 10: Строка 10:
 
       Tree_walt(x.right);
 
       Tree_walt(x.right);
 
Данный алгоритм выполняет обход за время <tex>O(n)</tex>, поскольку процедура вызывается ровно два раза для каждого узла дерева. Корректность данного алгоритма следует из свойств бинарного дерева поиска.  
 
Данный алгоритм выполняет обход за время <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> - высота дерева.
 
поиск минимума и максимума
 
поиск минимума и максимума
 
поиск следующего и предыдущего элемента
 
поиск следующего и предыдущего элемента

Версия 00:18, 20 марта 2011

Бинарное дерево поиска из 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], поскольку процедура вызывается ровно два раза для каждого узла дерева. Корректность данного алгоритма следует из свойств бинарного дерева поиска.

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

Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой.

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)

Приведенная выше функция принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы [math]O(h)[/math], где [math]h[/math] - высота дерева. поиск минимума и максимума поиск следующего и предыдущего элемента вставка удаление

Литература

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