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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''Бинарное дерево поиска''' - структура данных для работы с динамическими множествами. Бина…»)
 
Строка 1: Строка 1:
'''Бинарное дерево поиска''' - структура данных для работы с динамическими множествами.
+
'''Бинарное дерево поиска (англ. binary search tree, BST)''' - структура данных для работы с динамическими множествами.
 
Бинарное дерево поиска должно обладать следующим свойством: Если x - узел бинарного дерева с ключом k, то все узлы в левом поддереве должны иметь ключи, меньшие k, а в правом поддереве большие k.
 
Бинарное дерево поиска должно обладать следующим свойством: Если x - узел бинарного дерева с ключом k, то все узлы в левом поддереве должны иметь ключи, меньшие k, а в правом поддереве большие k.
 
== Операции в бинарном дереве поиска ==
 
== Операции в бинарном дереве поиска ==
обход дерева поиска
+
=== обход дерева поиска ===
 +
Имеется простой алгоритм вывода всех ключей бинарного дерева поиска в отсортированном порядке.
 +
Tree_walk(node x)
 +
  if(x != null)
 +
      Tree_walk(x.left);
 +
      print(x.key);
 +
      Tree_walt(x.right);
 
поиск элемента
 
поиск элемента
 
поиск минимума и максимума
 
поиск минимума и максимума

Версия 23:34, 19 марта 2011

Бинарное дерево поиска (англ. 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);

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

Литература

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