Дерево поиска, наивная реализация — различия между версиями
(Новая страница: «'''Бинарное дерево поиска''' - структура данных для работы с динамическими множествами. Бина…») |
|||
| Строка 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
