Изменения
→Реализация с использованием информации о родителе
=== Поиск следующего и предыдущего элемента ===
====Реализация с использованием информации о родителе====
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним предыдущий ему элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.
'''Node''' next(x : '''Node'''):
'''if''' x.right != ''null''
'''return''' y
Обе операции выполняются за время <tex>O(h)</tex>.
====Реализация без использования информации о родителе====
Рассмотрим поиск следующего элемента для некоторого ключа <tex>x</tex>. Поиск будем начинать с корня дерева, храня текущий узел <tex>current</tex> и узел <tex>successor</tex>, последний посещенный узел, ключ которого больше <tex>x</tex>. <br>
successor.right.parent = successor.parent
'''else'''
successor.parent.right = successor.rightleft '''if''' successor.right left != ''null''
successor.right.parent = successor.parent
====Рекурсивная реализация====
При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить '''этот''' минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <tex>O(h)</tex>.
Рекурсивная функция, возвращающая дерево с удаленным элементом <tex>z</tex>:
'''Node''' delete(root : '''Node''', z : '''T'''): <font color="green">// корень поддерева, удаляемый ключ</font>
'''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 if''' root.right != ''null''
root = root.right
'''else'''
root = root.right''null''
'''return''' root
|definition = Определить, является ли заданное двоичное дерево деревом поиска.
}}
[[Файл:Not_Enough.png|right|thumb|301px291px|Пример дерева, для которого недостаточно проверки лишь его соседейсоседних вершин]]Для того чтобы решить эту задачу, применим [[Обход в глубину, цвета вершин|обход в глубину]]. Запустим от корня рекурсивную логическую функцию, которая выведет <tex>\mathtt{true}</tex>, если дерево является BST и <tex>\mathtt{false}</tex> в противном случае. Чтобы дерево не являлось BST, в нём должна быть хотя бы одна вершина, которая не попадает под определение дерева поиска. То есть достаточно найти всего одну такую вершину, чтобы выйти из рекурсии и вернуть значение <tex>\mathtt{false}</tex>. Если же, дойдя до листьев, функция не встретит на своём пути такие вершины, она вернёт значение <tex>\mathtt{true}</tex>.
===Поиск Задачи на поиск максимального поддерева, являющегося BST, в заданном двоичном дереве===
{{Задача
|definition = Найти в данном дереве максимальное из поддеревьев такую вершину, что она будет корнем поддерева поискас наибольшим количеством вершин.
}}
Введём <tex>\mathtt{v.min}</tex> и <tex>\mathtt{v.max}</tex>, которые будут хранить минимум в левом поддереве вершины и максимум в правом. Тогда мы должны будем проверить, являются ли эти поддеревья деревьями поиска и, если да, лежит ли ключ вершины <tex>\mathtt{v}</tex> между этими значениями <tex>\mathtt{v.min}</tex> и <tex>\mathtt{v.max}</tex>. '''Node''' rootЕсли вершина является листом, она автоматически становится деревом поиска, а её ключ {{---}} минимумом или максимумом для её родителя (в зависимости от расположения вершины) maxdp = -1 maxroot = ''null'' '''for''' u '''in''' Tree . Функция <font color="green"tex>\mathtt{cnt}<// Здесь Tree — заданное двоичное деревоtex> записывает в <tex>\mathtt{v.kol}</fonttex> dp = dfs(uколичество вершин в дереве, если оно является деревом поиска или <tex> \mathtt{-\infty 1}</tex>, в противном случае. После выполнения функции ищем за линейное время вершину с наибольшим значением <tex> \infty mathtt{v.kol}</tex>) '''if''' dp > maxdp maxdp = dp maxroot = u '''return''' maxroot.
===Восстановление дерева по результату обхода preorderTraversal===
|definition = Восстановить дерево по последовательности, выведенной после выполнения процедуры <tex>\mathrm{preorderTraversal}</tex>.
}}
[[Файл:BST_from_seq.gif|right|thumb|257px|Восстановление дерева поиска по последовательности ключей]]
Как мы помним, процедура <tex>\mathrm{preorderTraversal}</tex> выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем на каком-то моменте делает шаг вправо и снова движется влево. Это продолжается до тех пор, пока не будут выведены все вершины. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения, будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём номер, нарушающий убывающую последовательность, а для каждого такого номера будем искать вершину без правого потомка, хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней элемент с таким номером в качестве правого сына. Когда мы, желая найти такую вершину, встречаем какую-нибудь другую, уже имеющую правого сына, проходим по ветке вправо. Мы имеем на это право, так как если такая вершина стоит, то процедура обхода в ней уже побывала и поворачивала вправо, поэтому спускаться в другую сторону смысла не имеет. Вершину с максимальным ключом, с которой будем начинать поиск, будем запоминать. Она будет обновляться каждый раз, когда появится новый максимум.
Разберём алгоритм на примере последовательности для приведённого выше дерева<tex>\mathtt{8}</tex> <tex>\mathtt{2}</tex> <tex>\mathtt{1}</tex> <tex>\mathtt{4}</tex> <tex>\mathtt{3}</tex> <tex>\mathtt{5}</tex>. Будем выделять красным цветом вершины, рассматриваемые на каждом шаге, чёрным жирным {{---}} их родителей, курсивом {{---}} убывающие подпоследовательности (в случаях, когда мы их рассматриваем) или претендентов на добавление к ним правого ребёнка (когда рассматривается вершина, нарушающая убывающую последовательность).{| style="background-color:#CCC;margin:0. Она выглядит так5px"!style="background-color:#EEE"| Состояние последовательности!style="background-color:#EEE"| Действие!style="background-color:#EEE"| Пояснение|-|style="background-color:#FFF;padding:2px 10px"| <span style="color: red">'''8 '''</span> 2 1 4 3 5|style="background-color:#FFF;padding:2px 10px"| Делаем вершину корнем.|style="background-color:#FFF;padding:2px 10px"| ''Первая вершина всегда будет корнем, так как вывод начинался с него. Сначала в корень записывается ''|-|style="background-color:#FFF;padding:2px 10px"| '''''8''''' <span style="color:red">'''''2'''''</span> ''1'' 4 3 5|rowspan=2 style="background-color:#FFF;padding:2px 10px"|Находим убывающую подпоследовательность. Каждую вершину подвешиваем к последней из взятых ранее в качестве левого сына. Затем его |rowspan=2 style="background-color:#FFF;padding:2px 10px"| ''Каждая последующая вершина становится левым сыном становится вершина с номером предыдущей, так как выводя ключи, мы двигались по дереву поиска влево, пока есть вершины.''|-| style="background-color:#FFF;padding:2px 10px"| ''8 '''2'', а её левым сыном — ''' <span style="color:red">'''''1''. Следующее значение — '''</span> 4 3 5|-|style="background-color:#FFF;padding:2px 10px"| ''8 '''2''''' 1 <span style="color:red">'''4'' — '</span> 3 5|style="background-color:#FFF;padding:2px 10px"| Для вершины, нарушившей убывающую последовательность, ищем максимальное значение, меньшее его. В данном случае оно равно <tex>\mathtt{2}</tex>. Затем добавляем вершину.|style="background-color:#FFF;padding:2px 10px"| ''На моменте вывода следующего номера процедура обратилась уже к какому-то из правых поддеревьев, так как влево идти уже нарушает убывающую подпоследовательностьнекуда. Подберём Значит, нам необходимо найти узел, для него которого данная вершина являлась бы правым сыном. Очевидно, что в её родителе не может лежать значение, которое больше её ключа. Но эту вершинунельзя подвесить и к меньшим, где лежит иначе нашёлся бы более старший предок, также хранящий какое-то значение, меньшее егокоторое меньше, причём такая чем в исследуемой. Для этого предка вершина максимальна (бы попала в противном случае левое поддерево. И тогда возникает противоречие с определением дерева поиска. Отсюда следует, что родитель определяется единственным образом {{---}} он будет превосходить и прародителяхранит максимум среди ключей, находясь не превосходящих значения в его левом поддеревеподвешиваемой вершине, а это противоречит определению дерева поиска)что и требовалось доказать. Это узел с числом ''|-|style="background-color:#FFF;padding:2px 10px"| 8 21 '''''4''''' <span style="color:red">'''''3'''''</span> 5|style="background-color:#FFF;padding:2px 10px"| Находим убывающую подпоследовательность. Сделаем его правым сыном рассматриваемую Каждую вершинуподвешиваем к последней из взятых ранее в качестве левого сына. Затем |style="background-color:#FFF;padding:2px 10px"| ''Зайдя в правое поддерево, процедура обхода снова дадим левых потомков последней добавленной вершинедо упора начала двигаться влево, опять же, пока не найдём ключ, нарушающий порядок убыванияпоэтому действуем аналогичным образом. В нашем случае в дерево дописывается ''3|-|style="background-color:#FFF;padding:2px 10px"| ''8'' 2 1 '''. Для следующего значения снова ищем родителя, для которого он станет правым сыном. Это значение равно ''4''. Добавляем ''' 3 <span style="color:red">'''5'' как правого сына для '</span>|style="background-color:#FFF;padding:2px 10px"| Для этой вершины ищем максимальное значение, меньшее его. Затем добавляем вершину.|style="background-color:#FFF;padding:2px 10px"| ''Здесь процедура снова обратилась к правому поддереву. Рассуждения аналогичны. Ключ родителя этой вершины равен <tex>\mathtt{4}</tex>.''. Итак, мы построили дерево.|}
==См. также==
* [[Рандомизированное бинарное дерево поиска]]
* [[Красно-черное дерево]]
==Источники информации==
* [https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0 Википедия {{---}} Двоичное дерево поиска]