Дерево поиска, наивная реализация
Бинарное дерево поиска обладает следующим свойством: если — узел бинарного дерева с ключом , то все узлы в левом поддереве должны иметь ключи, меньшие , а в правом поддереве большие .
Операции в бинарном дереве поиска
Для представления бинарного дерева поиска в памяти будем использовать следующую структуру:
struct Node: T key // ключ узла Node left // указатель на левого потомка Node right // указатель на правого потомка Node parent // указатель на предка
Обход дерева поиска
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:
- — обход узлов в отсортированном порядке,
- — обход узлов в порядке: вершина, левое поддерево, правое поддерево,
- — обход узлов в порядке: левое поддерево, правое поддерево, вершина.
func inorderTraversal(x : Node):
if x != null
inorderTraversal(x.left)
print x.key
inorderTraversal(x.right)
При выполнении данного обхода вершины будут выведены в следующем порядке: 1 3 4 6 7 8 10 13 14.
func preorderTraversal(x : Node)
if x != null
print x.key
preorderTraversal(x.left)
preorderTraversal(x.right)
При выполнении данного обхода вершины будут выведены в следующем порядке: 8 3 1 6 4 7 10 14 13.
func postorderTraversal(x : Node)
if x != null
postorderTraversal(x.left)
postorderTraversal(x.right)
print x.key
При выполнении данного обхода вершины будут выведены в следующем порядке: 1 4 7 6 3 13 14 10 8.
Данные алгоритмы выполняют обход за время , поскольку процедура вызывается ровно два раза для каждого узла дерева.
Поиск элемента
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей процедурой, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы , где — высота дерева.
Node search(x : Node, k : T):
if x == null or k == x.key
return x
if k < x.key
return search(x.left, k)
else
return search(x.right, k)
Поиск минимума и максимума
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям от корня дерева, пока не встретится значение . Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.
Node minimum(x : Node):
if x.left == null
return x
return minimum(x.left)
Node maximum(x : Node):
if x.right == null
return x
return maximum(x.right)
Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время .
Поиск следующего и предыдущего элемента
Реализация с использованием информации о родителе
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.
Node next(x : Node):
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(x : Node):
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
Обе операции выполняются за время .
Реализация без использования информации о родителе
Рассмотрим поиск следующего элемента для некоторого ключа . Поиск будем начинать с корня дерева, храня текущий узел и узел , последний посещенный узел, ключ которого больше .
Спускаемся вниз по дереву, как в алгоритме поиска узла. Рассмотрим ключ текущего узла . Если , значит следующий за узел находится в правом поддереве (в левом поддереве все ключи меньше ). Если же , то , поэтому может быть следующим для ключа , либо следующий узел содержится в левом поддереве . Перейдем к нужному поддереву и повторим те же самые действия.
Аналогично реализуется операция поиска предыдущего элемента.
Node next(x : T):
Node current = root, successor = null // root — корень дерева
while current != null
if current.key > x
successor = current
current = current.left
else
current = current.right
return successor
Вставка
Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент.
Реализация с использованием информации о родителе
func insert(x : Node, z : Node): // x — корень поддерева, z — вставляемый элемент
while x != null
if z.key > x.key
if x.right != null
x = x.right
else
z.parent = x
x.right = z
break
else if z.key < x.key
if x.left != null
x = x.left
else
z.parent = x
x.left = z
break
Реализация без использования информации о родителе
Node insert(x : Node, z : T): // x — корень поддерева, z — вставляемый ключ
if x == null
return Node(z) // подвесим Node с key = z
else if z < x.key
x.left = insert(x.left, z)
else if z > x.key
x.right = insert(x.right, z)
return x
Время работы алгоритма для обеих реализаций — .
Удаление
Нерекурсивная реализация
Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на . Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент (у этого элемента не будет левого потомка), его правого потомка подвесить на место найденного элемента, а удаляемый узел заменить найденным узлом. Таким образом, свойство бинарного дерева поиска не будет нарушено. Данная реализация удаления не увеличивает высоту дерева. Время работы алгоритма — .
| Случай | Иллюстрация |
|---|---|
| Удаление листа | 
|
| Удаление узла с одним дочерним узлом | 
|
| Удаление узла с двумя дочерними узлами | 
|
func delete(t : Node, v : Node): // — дерево, — удаляемый элемент p = v.parent // предок удаляемого элемента if v.left == null and v.right == null // первый случай: удаляемый элемент - лист if p.left == v p.left = null if p.right == v p.right = null else if v.left == null or v.right == null // второй случай: удаляемый элемент имеет одного потомка if v.left == null if p.left == v p.left = v.right else p.right = v.right v.right.parent = p else if p.left == v p.left = v.left else p.right = v.left v.left.parent = p else // третий случай: удаляемый элемент имеет двух потомков successor = next(v, t) v.key = successor.key if successor.parent.left == successor successor.parent.left = successor.right if successor.right != null successor.right.parent = successor.parent else successor.parent.right = successor.right if successor.right != null successor.right.parent = successor.parent
Рекурсивная реализация
При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма — . Рекурсивная функция, возвращающая дерево с удаленным элементом :
Node delete(root : Node, z : T): // корень поддерева, удаляемый ключ
if root == null
return root
if z < root.key
root.left = delete(root.left, z)
else if z > root.key
root.right = delete(root.right, z)
else if root.left != null and root.right != null
root.key = minimum(root.right).key
root.right = delete(root.right, root.right.key)
else
if root.left != null
root = root.left
else
root = root.right
return root
Поиск максимального поддерева, являющегося BST, в заданном двоичном дереве
В переменную , изначально равную , запишем число вершин максимального поддерева поиска. Будем также вместе с обновлять , где будет храниться корень такого поддерева. Чтобы найти , обойдём вершины и для каждой из них с помощью процедуры , на вход которой подаются сама вершина, максимально и минимально возможные элементы поддерева и количество вершин, посчитаем число элементов, принадлежащих максимальному дереву поиска, для которого данная вершина является корнем. Если результат после обхода вершины оказался больше значения в переменной , обновляем и . Затем переходим к следующей вершине. После того как мы прошлись по всему дереву, посчитали и нашли , запускаем процедуру для вывода вершин поддерева поиска. До запуска процедур и переменная равна единице.
maxdp = -1
maxroot = null
for u in Tree // Здесь Tree – заданное двоичное дерево.
dp = 1
dfs(u, -INF, INF, dp)
if(dp>maxdp)
maxdp = dp
maxroot = u
dfsPrint(maxroot,-INF,INF)
Функция возвращает максимальное количество вершин двоичного поддерева поиска с вершиной . В начале работы этой функции и принимают нейтральные значения ( и соответственно, где - очень большое число), а равен (одна вершина в дереве уже имеется). Обход осуществляется следующим образом:
1 шаг. Проверяем, есть ли у вершины левый сын. Если его нет, переходим к пункту 2, иначе сравниваем значения в этой вершине и в её левом потомке, а также значение в левом сыне с максимумом в поддереве. Если значение в левом сыне меньше, чем значение в вершине и больше переменной , то запускаем из левого сына. Здесь роль v будет разыгрывать , приобретёт значение , по-прежнему останется , а увеличится на 1. Пояснение: ключи вершин левого поддерева не должны превосходить значения в рассматриваемой вершине, поэтому мы изменяем . На эта вершина не влияет в случае левого поддерева, поэтому он не изменяется. увеличивается на 1, так как в наше поддерево добавилась ещё одна вершина.
2 шаг. Аналогично действуем с правым потомком. Проверяем его наличие. Если он существует, то сравниваем значение в нём с минимумом и с ключом вершины. Если значение правого сына больше минимума в поддереве и меньше значения в вершине, то запускаем от потомка . Теперь на место встаёт , остаётся прежним, становится ключом в рассматриваемой вершине, а снова увеличивается на 1. Для случая с правым поддеревом рассуждения аналогичны.
3 шаг. Возвращаем результат в переменной , где записано количество вершин поддерева.
Процедура обхода дерева представлена ниже:
procedure dfs(v: Node, max: T, min: T, res: integer)
if v.left != null
if v.left.key < v.key and v.left.key > max
dfs(v.left, v.left.key, min, res+1)
if v.right != null
if v.right.key > v.key and v.right.key < min
dfs(v.left, max, v.left.key, res+1)
Наконец, рассмотрим процедуру , выводящую максимальное дерево поиска. Так как уже посчитано, достаточно задать три параметра: корень поддерева и максимальное и минимальное допустимые значения. и нам понадобятся, чтобы взять только те вершины, которые принадлежат дереву.
procedure dfsPrint(v: Node, max: T, min: T)
print v.key
if v.left != null
if v.left.key < v.key and v.left.key > max
print v.left.key
dfs(v.left, v.left.key, min)
if v.right != null
if v.right.key > v.key and v.right.key < min
print v.right.key
dfs(v.left, max, v.left.key)
Заметим, что выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем делает шаг вправо, потом снова влево и так до тех пор, пока не будет выведено вершин. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Происходит это так:
- последовательно подвешиваем левых сыновей, пока не находим номер, нарушающий убывающую последовательность;
- для каждого номера, нарушающего убывающую последовательность, ищем вершину с наибольшим значением, не превосходящим его, среди вершин без правого потомка и к этому элементу подвешиваем вершину с таким номером в качестве правого сына.
Первое число последовательности всегда находится в корне, так как вывод ключей вершин начинался с него.
Разберём алгоритм на примере последовательности для приведённого выше дерева. Она выглядит так: 8 2 1 4 3 5. Сначала в корень записывается 8. Затем его левым сыном становится вершина с номером 2, а её левым сыном - 1. Следующее значение - 4 - уже нарушает убывающую подпоследовательность. Подберём для него вершину, где лежит значение, меньшее его, причём такая вершина максимальна (в противном случае он будет превосходить и прародителя, находясь в его левом поддереве, а это противоречит определению дерева поиска). Это узел с числом 2. Сделаем его правым сыном рассматриваемую вершину. Затем снова дадим левых потомков последней добавленной вершине, опять же, пока не найдём ключ, нарушающий порядок убывания. В нашем случае в дерево дописывается 3. Для следующего значения снова ищем родителя, для которого он станет правым сыном. Это значение равно 4. Добавляем 5 как правого сына для вершины 4. Итак, мы построили дерево.
Проверка BST
Чтобы ответить на вопрос, является ли данное двоичное дерево деревом поиска, необходимо запустить из корня. Если значение для него совпадает с количеством вершин в дереве, то есть все вершины вошли в бинарное дерево поиска с вершиной в корне исходного дерева, ответ "да", иначе – "нет".
См. также
Источники информации
- Википедия — Двоичное дерево поиска
- Wikipedia — Binary search tree
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
