243
правки
Изменения
Карлукова Марина, M3136 (дополнения)
====Рекурсивная реализация====
При рекурсивном удаления удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <tex>O(h)</tex>.
Рекурсивная функция, возвращающая дерево с удаленным элементом <tex>z</tex>:
'''Node''' delete(root : '''Node''', z : '''T'''): <font color="green">// корень поддерева, удаляемый ключ</font>
root = root.right
'''return''' root
==Поиск максимального поддерева, являющегося BST, в заданном двоичном дереве==
В переменную <tex>maxdp</tex>, изначально равную <tex>-1</tex>, запишем число вершин максимального поддерева поиска. Будем также вместе с <tex>maxdp</tex> обновлять <tex>maxroot</tex>, где будет храниться корень такого поддерева. Чтобы найти <tex>maxdp</tex>, обойдём вершины и для каждой из них с помощью процедуры <tex>dfs</tex>, на вход которой подаются сама вершина, максимально и минимально возможные элементы поддерева и количество вершин, посчитаем число элементов, принадлежащих максимальному дереву поиска, для которого данная вершина является корнем. Если результат после обхода вершины оказался больше значения в переменной <tex>maxdp</tex>, обновляем <tex>maxdp</tex> и <tex>maxroot</tex>. Затем переходим к следующей вершине. После того как мы прошлись по всему дереву, посчитали <tex>maxdp</tex> и нашли <tex>maxroot</tex>, запускаем процедуру <tex>dfsPrint(maxroot, -INF, INF)</tex> для вывода вершин поддерева поиска. До запуска процедур <tex>dfs</tex> и <tex>dfsPrint</tex> переменная <tex>dp</tex> равна единице.
maxdp = -1
maxroot = ''null''
'''for''' u '''in''' Tree <font color="green">// Здесь Tree – заданное двоичное дерево.</font>
dp = 1
dfs(u, -INF, INF, dp)
'''if'''(dp>maxdp)
maxdp = dp
maxroot = u
dfsPrint(maxroot,-INF,INF)
Функция <tex>dfs(v,max,min,res)</tex> возвращает максимальное количество вершин двоичного поддерева поиска с вершиной <tex>v</tex>. В начале работы этой функции <tex>max</tex> и <tex>min</tex> принимают нейтральные значения (<tex>-INF</tex> и <tex>INF</tex> соответственно, где <tex>INF</tex> - очень большое число), а <tex>res</tex> равен <tex>1</tex> (одна вершина в дереве уже имеется). Обход осуществляется следующим образом:
'''1 шаг.''' Проверяем, есть ли у вершины левый сын. Если его нет, переходим к пункту 2, иначе сравниваем значения в этой вершине и в её левом потомке, а также значение в левом сыне с максимумом в поддереве. Если значение в левом сыне меньше, чем значение в вершине и больше переменной <tex>max</tex>, то запускаем <tex>dfs</tex> из левого сына. Здесь роль v будет разыгрывать <tex>v.left</tex>, <tex>max</tex> приобретёт значение <tex>v.key</tex>, <tex>min</tex> по-прежнему останется <tex>min</tex>, а <tex>res</tex> увеличится на 1. ''Пояснение:'' ключи вершин левого поддерева не должны превосходить значения в рассматриваемой вершине, поэтому мы изменяем <tex>max</tex>. На <tex>min</tex> эта вершина не влияет в случае левого поддерева, поэтому он не изменяется. <tex>res</tex> увеличивается на 1, так как в наше поддерево добавилась ещё одна вершина.
'''2 шаг.''' Аналогично действуем с правым потомком. Проверяем его наличие. Если он существует, то сравниваем значение в нём с минимумом и с ключом вершины. Если значение правого сына больше минимума в поддереве и меньше значения в вершине, то запускаем от потомка <tex>dfs</tex>. Теперь на место <tex>v</tex> встаёт <tex>v.right</tex>, <tex>max</tex> остаётся прежним, <tex>min</tex> становится ключом в рассматриваемой вершине, а <tex>res</tex> снова увеличивается на 1. Для случая с правым поддеревом рассуждения аналогичны.
'''3 шаг.''' Возвращаем результат в переменной <tex>res</tex>, где записано количество вершин поддерева.
[[Файл:BST_in_Tree.gif|centre|Пример выполнения процедуры dfs (из корневой вершины дерева)]]
Процедура обхода дерева представлена ниже:
'''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)
Наконец, рассмотрим процедуру <tex>dfsPrint</tex>, выводящую максимальное дерево поиска. Так как <tex>maxdp</tex> уже посчитано, достаточно задать три параметра: корень поддерева и максимальное и минимальное допустимые значения. <tex>max</tex> и <tex>min</tex> нам понадобятся, чтобы взять только те вершины, которые принадлежат дереву.
'''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)
[[Файл:BST_from_sequence.gif|right|Восстановление дерева поиска по последовательности ключей]]
Заметим, что <tex>dfsPrint</tex> выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем делает шаг вправо, потом снова влево и так до тех пор, пока не будет выведено <tex>maxdp</tex> вершин. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Происходит это так:
- последовательно подвешиваем левых сыновей, пока не находим номер, нарушающий убывающую последовательность;
- для каждого номера, нарушающего убывающую последовательность, ищем вершину с наибольшим значением, не превосходящим его, среди вершин без правого потомка и к этому элементу подвешиваем вершину с таким номером в качестве правого сына.
Первое число последовательности всегда находится в корне, так как вывод ключей вершин начинался с него.
Разберём алгоритм на примере последовательности для приведённого выше дерева. Она выглядит так: ''8 2 1 4 3 5''. Сначала в корень записывается ''8''. Затем его левым сыном становится вершина с номером ''2'', а её левым сыном - ''1''. Следующее значение - ''4'' - уже нарушает убывающую подпоследовательность. Подберём для него вершину, где лежит значение, меньшее его, причём такая вершина максимальна (в противном случае он будет превосходить и прародителя, находясь в его левом поддереве, а это противоречит определению дерева поиска). Это узел с числом ''2''. Сделаем его правым сыном рассматриваемую вершину. Затем снова дадим левых потомков последней добавленной вершине, опять же, пока не найдём ключ, нарушающий порядок убывания. В нашем случае в дерево дописывается ''3''. Для следующего значения снова ищем родителя, для которого он станет правым сыном. Это ''4''. Добавляем ''5'' как правого сына для вершины ''4''. Итак, мы построили дерево.
===Проверка BST===
Чтобы ответить на вопрос, является ли данное двоичное дерево деревом поиска, необходимо запустить <tex>dfs</tex> из корня. Если значение для него совпадает с количеством вершин в дереве, то есть все вершины вошли в бинарное дерево поиска с вершиной в корне исходного дерева, ответ ''"да"'', иначе – ''"нет"''.
==См. также==
