Дерево поиска, наивная реализация
Бинарное дерево поиска обладает следующим свойством: если
- узел бинарного дерева с ключом , то все узлы в левом поддереве должны иметь ключи, меньшие , а в правом поддереве большие .Операции в бинарном дереве поиска
Обход дерева поиска
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:
- inorderTraversal - обход узлов в отсортированном порядке
- prefixTraversal - обход узлов в порядке: вершина, левое поддерево, правое поддерево
- postfixTraversal - обход узлов в порядке: левое поддерево, правое поддерево, вершина
inorderTraversal(Node x) if x != null inorderTraversal(x.left) print(x.key) inorderTraversal(x.right)
Корректность данного алгоритма следует из свойств бинарного дерева поиска.
prefixTraversal(Node x) if x != null print(x.key) prefixTraversal(x.left) prefixTraversal(x.right)
postfixTraversal(Node x) if x != null postfixTraversal(x.left) postfixTraversal(x.right) print(x.key)
Данные алгоритмы выполняют обход за время
, поскольку процедура вызывается ровно два раза для каждого узла дерева.Поиск элемента
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы
, где - высота дерева.Node search(Node x, key k) if x == null or k == x.key return x if k < x.key return search(x.left, k) else return search(x.right, k)
Поиск минимума и максимума
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям left от корня дерева, пока не встретится значение null. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.
Node minimum(Node x) while x.left != null x = x.left return x
Node maximum(Node x) while x.right != null x = x.right return x
Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время
.Поиск следующего и предыдущего элемента
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.
Node next(Node x) if x.right != null return minimum(x.right) y = x.parent while y != null and x == y.right x = y y = y.parent return y
Node prev(Node x) if x.left != null return maximum(x.left) y = x.parent while y != null and x == y.left x = y y = y.parent return y
Обе операции выполняются за время
.Вставка
Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент. Приведем итеративную реализацию этого алгоритма.
insert(Node x, Node z) // корень поддерева, вставляемый элемент Node y = null while x != null y = x if z.key > x.key x = x.right else x = x.left z.parent = y if z.key > y.key y.right = z else y.left = z
Время работы алгоритма
.Удаление
Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на null. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент(у этого элемента не будет левого потомка) и переместить его на место удаляемого узла. Время работы алгоритма
.Случай | Иллюстрация |
---|---|
Удаление листа | ![]() |
Удаление узла с одним дочерним узлом | ![]() |
Удаление узла с двумя дочерними узлами | ![]() |
Удаление корня | ![]() |
delete(Node root, Node z) //корень дерева, удаляемый элемент Node x, y if z.left == null or z.right == null //y - удаляемый элемент, если тот имеет не более одного ребенка y = z else //иначе - следующий за ним y = next(z) if y.left != null //x - ребенок y x = y.left else x = y.right if x != null //подвешиваем x вместо y x.parent = y.parent if y.parent == null root = x else if y == y.parent.left y.parent.left = x else y.parent.right = x if y != z //если y - не удаляемый, а следующий за ним, то меняем z на y z.key = y.key z.data = y.data
Ссылки
Литература
1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4