Дерево поиска, наивная реализация
Бинарное дерево поиска обладает следующим свойством: если — узел бинарного дерева с ключом , то все узлы в левом поддереве должны иметь ключи, меньшие , а в правом поддереве большие .
Операции в бинарном дереве поиска
Для представления бинарного дерева поиска в памяти будем использовать следующую структуру:
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
dfsPrint(v.left, v.left.key, min)
if v.right != null
if v.right.key > v.key and v.right.key < min
dfsPrint(v.left, max, v.left.key)
Заметим, что выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем делает шаг вправо, потом снова влево и так до тех пор, пока не будет выведено вершин. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Происходит это так:
- последовательно подвешиваем левых сыновей, пока не находим номер, нарушающий убывающую последовательность;
- для каждого номера, нарушающего убывающую последовательность, ищем вершину с наибольшим значением, не превосходящим его, среди вершин без правого потомка и к этому элементу подвешиваем вершину с таким номером в качестве правого сына.
Первое число последовательности всегда находится в корне, так как вывод ключей вершин начинался с него.
Разберём алгоритм на примере последовательности для приведённого выше дерева. Она выглядит так: 8 2 1 4 3 5. Сначала в корень записывается 8. Затем его левым сыном становится вершина с номером 2, а её левым сыном - 1. Следующее значение - 4 - уже нарушает убывающую подпоследовательность. Подберём для него вершину, где лежит значение, меньшее его, причём такая вершина максимальна (в противном случае он будет превосходить и прародителя, находясь в его левом поддереве, а это противоречит определению дерева поиска). Это узел с числом 2. Сделаем его правым сыном рассматриваемую вершину. Затем снова дадим левых потомков последней добавленной вершине, опять же, пока не найдём ключ, нарушающий порядок убывания. В нашем случае в дерево дописывается 3. Для следующего значения снова ищем родителя, для которого он станет правым сыном. Это значение равно 4. Добавляем 5 как правого сына для вершины 4. Итак, мы построили дерево.
См. также
Источники информации
- Википедия — Двоичное дерево поиска
- Wikipedia — Binary search tree
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
