Изменения

Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним предыдущий ему элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.

successor.parent.right = successor.rightleft '''if''' successor.right left != ''null''

При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить '''этот''' минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <tex>O(h)</tex>.

root.right = delete(root.right, root.right.key)

root = root.right''null''

===Проверка того, что заданное дерево является деревом поиска===

[[Файл:Not_Enough.png|right|thumb|291px|Пример дерева, для которого недостаточно проверки лишь его соседних вершин]]Для того чтобы решить эту задачу, применим [[Обход в глубину, цвета вершин|обход в глубину]]. Запустим от корня рекурсивную логическую функцию, которая выведет <tex>\mathtt{true}</tex>, если дерево является BST и <tex>\mathtt{false}</tex> в противном случае. Чтобы дерево не являлось BST, в нём должна быть хотя бы одна вершина, которая не попадает под определение дерева поиска. То есть достаточно найти всего одну такую вершину, чтобы выйти из рекурсии и вернуть значение <tex>\mathtt{false}</tex>. Если же, дойдя до листьев, функция не встретит на своём пути такие вершины, она вернёт значение <tex>\mathtt{true}</tex>.

'''bool''' check(v Функция принимает на вход исследуемую вершину, а также два значения: '''Node''', <tex>\mathtt{min: '''integer'''}</tex> и <tex>\mathtt{max}</tex>, max: '''integer'''): которые до вызова функции равнялись <font color="green"tex>\infty <//min tex> и max <tex> - минимально и максимально допустимые значения в вершинах поддерева.\infty </tex> соответственно, где <tex> \infty </fonttex> '''if''' v— очень большое число, т.left != ''null'' '''if''' vе.leftни один ключ дерева не превосходит его по модулю.key > vКазалось бы, два последних параметра не нужны.key '''or''' vНо без них программа может выдать неверный ответ, так как сравнения только вершины и её детей недостаточно.leftНеобходимо также помнить, в каком поддереве для более старших предков мы находимся.key Например, в этом дереве вершина с номером < min '''return''' false '''else''' check(v.lefttex>8</tex> находится левее вершины, min, v.key) '''if''' v.right.key в которой лежит <tex>5< v.key '''or''' v.right.key /tex> max '''return''' false '''else''' check(v.right, v.keyчего не должно быть в дереве поиска, max) '''return''' однако после проверки функция бы вернула <tex>\mathtt{true}</tex>.

'''bool''' isBinarySearchTree(root: '''Node'''): <font color="green">// Здесь root — корень заданного двоичного дерева.</font> '''bool''' check(v : '''Node''', min: '''T''', max: '''T'''): <font color="green">// min и max — минимально и максимально допустимые значения в вершинах поддерева.</font> '''if''' v == ''null'' '''return''' ''true'' '''if''' v.key <=min '''or''' max <=Поиск v.key '''return''' ''false'' '''return''' check(v.left, min, v.key) '''and''' check(v.right, v.key, max) '''return''' check(root, <tex> -\infty </tex>, <tex> \infty </tex>) Время работы алгоритма {{---}} <tex>O(n)</tex>, где <tex>n</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>. Вместе с Если вершина является листом, она автоматически становится деревом поиска, а её ключ {{---}} минимумом или максимумом будем запоминать и соответствующую ему вершинудля её родителя (в зависимости от расположения вершины). Функция <tex>\mathtt{cnt}</tex> записывает в <tex>\mathtt{v. После тогоkol}</tex> количество вершин в дереве, как мы обошли всё дерево и нашли корень дерева если оно является деревом поиска или <tex>\mathtt{-1}</tex> в противном случае. После выполнения функции ищем за линейное время вершину с наибольшим количеством вершин, запускаем процедуру, выводящую все вершины на экранзначением <tex>\mathtt{v.kol}</tex>.

'''int''' count(root: '''Node''' ): <font color="green">// root— корень заданного двоичного дерева.</font> '''int''' cnt(v: '''Node'''): '''if''' v == ''null'' v.kol = 0 maxdp '''return''' = 0 '''if''' cnt(v.left) != -1 '''and''' cnt(v.right) != -1 maxroot '''if''' v.left == ''null'' '''and''' v.right == ''null'' v.min = v.key v.max = v.key v.kol = 1 '''forreturn''' u 1 '''inif''' Tree <font colorv.left =="green"''null'' '''if''' v.right.max >// Здесь Tree – заданное двоичное деревоv.key v.min = v.key v.kol = cnt(v.right) + 1 '''return''' v.kol '''if''' v.right == ''null'' '''if''' v.left.min </font>v.key v.max = v.key dp v.kol = dfscnt(u, <tex> -\infty </tex>, <tex> \infty </tex>v.left)+ 1 '''return''' v.kol '''if''' dp v.left.min < v.key '''and''' v.right.max > maxdpv.key maxdp v.min = v.left.min v.max = v.right.max v.kol = dpv.left.kol + v.right.kol + 1 maxroot v.kol = ucnt(v.left) + cnt(v.right) + 1 '''return''' v.kol '''return''' -1 '''return''' maxrootcnt(root)

Функция Алгоритм работает за <tex>\mathtt{dfs}O(n)</tex> позволяет найти для каждой вершин максимально возможное количество узлов поддерева. На вход функции подаются сама анализируемая вершина и левая и правая границы интервала, в которой могут находиться значения в её поддереве. Начальные значения двух последних аргументов равны <tex> -\infty </tex> и <tex> \infty </tex> соответственнотак как мы прошлись по дереву два раза за время, где <tex> \infty </tex> - очень большое число, т.е. ни один ключ дерева не превосходит его по модулюравное количеству вершин.

В основе функции также лежит [[Обход в глубину, цвета вершин|обход в глубину]]. Рекурсивная функция обходит всех существующих детей вершины, поданной на вход, и, если ребёнок не нарушает условия ===Восстановление дерева поиска, она добавляет его в поддерево и анализирует его потомков. В этом случае роль <tex>v</tex> будет разыгрывать ребёнок, удовлетворяющий условию дерева поиска. Если он был левым сыном, то максимально возможному значению присваивается число, стоящее в его родителе, а минимальное возможное значение не изменяется. Наоборот, если он был правым сыном, увеличиваем минимум, а максимум оставляем тем же. В случае, когда левый или правый сын не удовлетворяет условию дерева поиска, этот узел не включается в искомое поддерево и дальше не рассматривается.по результату обхода preorderTraversal===

Функция возвращает значение переменной <tex>\mathtt{res}</tex>, где записано количество вершин поддерева.  '''int''' dfs(v: '''Node''', max: '''T''', min: '''T'''){Задача res |definition = 1 '''if''' v.left != ''null'' '''if''' v.left.key < v.key '''and''' v.left.key > max res += dfs(v.left, v.left.keyВосстановить дерево по последовательности, min) '''if''' v.right != ''null'' '''if''' v.right.key > v.key '''and''' v.right.key < min res += dfs(v.left, max, v.left.key) '''return''' res Наконец, рассмотрим процедуру выведенной после выполнения процедуры <tex>\mathttmathrm{dfsPrintpreorderTraversal}</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 dfsPrint(v.left, v.left.key, min) '''if''' vBST_from_seq.gif|right != ''null'' '''if''' v.right.key > v.key '''and''' v.right.key < min dfsPrint(v.left, max, v.left.key)|thumb|257px|Восстановление дерева поиска по последовательности ключей]]

[[ФайлКак мы помним, процедура <tex>\mathrm{preorderTraversal}</tex> выводит значения в узлах поддерева следующим образом:BST_from_seqсначала идёт до упора влево, затем на каком-то моменте делает шаг вправо и снова движется влево.gif|right|thumb|300px|Восстановление дерева поиска Это продолжается до тех пор, пока не будут выведены все вершины. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения, будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём номер, нарушающий убывающую последовательность, а для каждого такого номера будем искать вершину без правого потомка, хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней элемент с таким номером в качестве правого сына. Когда мы, желая найти такую вершину, встречаем какую-нибудь другую, уже имеющую правого сына, проходим по последовательности ключей]]ветке вправо. Мы имеем на это право, так как если такая вершина стоит, то процедура обхода в ней уже побывала и поворачивала вправо, поэтому спускаться в другую сторону смысла не имеет. Вершину с максимальным ключом, с которой будем начинать поиск, будем запоминать. Она будет обновляться каждый раз, когда появится новый максимум.

Заметим, что Процедура восстановления дерева работает за <tex>dfsPrintO(n)</tex> выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем делает шаг вправо, потом снова влево и так до тех пор, пока не будет выведено <tex>maxdp</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">'2'', а её левым сыном - ''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>.''. Итак, мы построили дерево.|}

* [[АВЛ-дерево]]