Дерево поиска, наивная реализация
Бинарное дерево поиска должно обладать следующим свойством: Если
- узел бинарного дерева с ключом , то все узлы в левом поддереве должны иметь ключи, меньшие или равные , а в правом поддереве большие .Операции в бинарном дереве поиска
обход дерева поиска
Имеется простой алгоритм вывода всех ключей бинарного дерева поиска в отсортированном порядке.
Tree_walk(node x) if(x != null) Tree_walk(x.left); print(x.key); Tree_walt(x.right);
Данный алгоритм выполняет обход за время
, поскольку процедура вызывается ровно два раза для каждого узла дерева. Корректность данного алгоритма следует из свойств бинарного дерева поиска.Поиск элемента
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой.
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);
Приведенная выше функция принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы
, где - высота дерева.Поиск минимума и максимума
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям left от корня дерева, пока не встретится значение hull. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.
Tree_min(root x) while (x.left != null) x = x.left; return x;
Tree_max(root x) while (x.right != null) x = x.right; return x;
Данные функции принимают корень дерева, и возвращают минимальный(максимальный) элемент в дереве. Обе процедуры выполняются за время
.Поиск следующего и предыдущего элемента
Tree_next(root x) if (x.right != null) return Tree_min(x.right); y = x.parent; while(y != null and x == y.right) x = y; y = y.parent; return y;
Tree_prev(root x) if (x.left != null) return Tree_max(x.left); y = x.parent; while(y != null and x == y.left) x = y; y = y.parent; return y;
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя. Обе операции выполняются за время
.Вставка
Операция вставки работает аналогично поиску элемента, только при обнаружении нулевого указателя нужно подвесить на него вставляемый элемент. Приведем итеративную реализацию этого алгоритма.
Tree_insert(root x, root z) // корень дерева, вставляемый элемент root 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. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент(у этого элемента не будет левого потомка) и переместить его на место удаляемого узла.
случай | Иллюстрация |
---|---|
Удаление листа | ![]() |
Удаление узла с одним дочерним узлом | ![]() |
Удаление узла с двумя дочерними узлами | ![]() |
Удаление корня | ![]() |
Tree_delete(root t, root z) // корень дерева, вставляемый элемент root x, y; if(z.left == null or z.right == null) y = z; else y = Tree_next(z); if(y.left != null) x = y.left; else x = y.right; if(x != null) x.parent = y.parent; if(y.parent == null) t = x; else if(y == y.parent.left) y.parent.left = x; else y.parent.right = x; if(y != z) z.key = y.key; z.data = y.data; return y;
Литература
1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4