Изменения

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

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

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

root = root.right''null''

Функция принимает на вход исследуемую вершину, а также два значения: <tex>\mathtt{min}</tex> и <tex>\mathtt{max}</tex>, которые до вызова функции равнялись <tex> \infty </tex> и <tex> -\infty </tex> соответственно, где <tex> \infty </tex> — очень большое число, т.е. ни один ключ дерева не превосходит его по модулю. Казалось бы, два последних параметра не нужны. Но без них программа может выдать неверный ответ, так как сравнения только вершины и её детей недостаточно. Необходимо также помнить, в каком поддереве для более старших предков мы находимся. Например, в этом дереве вершина с номером ''<tex>8'' </tex> находится левее вершины, в которой лежит ''<tex>5''</tex>, чего не должно быть в дереве поиска, однако после проверки функция бы вернула <tex>\mathtt{true}</tex>.

'''bool''' isBinarySearchTree(root: '''Node'''): <font color="green">// Здесь root — корень заданного двоичного дерева.</font> '''bool''' check(v : '''Node''', min: '''intT''', max: '''intT'''): <font color="green">// min и max — минимально и максимально допустимые значения в вершинах поддерева.</font> '''if''' v.left !== ''null'' '''return''' ''true'' '''if''' v.left.key > v.key <= min '''or''' max <= v.left.key < min '''return''' ''false'' '''else''' '''return''' check(v.left, min, v.key) '''ifand''' check(v.right != ''null'' '''if''' v.right.key < , v.key '''or''' v.right.key > , max) '''return''' ''false'' '''else''' '''return''' check(v.rightroot, v.key<tex> -\infty </tex>, max<tex> \infty </tex>) '''return''' ''true''Время работы алгоритма {{---}} <tex>O(n)</tex>, где <tex>n</tex> {{---}} количество вершин в дереве.

|definition = Найти в данном дереве такую вершину, что поддерево, для которого она является будет корнем, максимальноподдерева поиска с наибольшим количеством вершин.

Введём <tex>\mathtt{v.min}</tex> и <tex>\mathtt{Задача|definition = Выделить 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>\mathrmmathtt{preorderTraversalv.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 = dpv.right.max maxroot v.kol = v.left.kol + v.right.kol + 1 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>v</tex> будет разыгрывать ребёнок, удовлетворяющий условию дерева поиска. Если он был левым сыном, то максимально возможному значению присваивается число, стоящее в его родителе, а минимальное возможное значение не изменяется. Наоборот, если он был правым сыном, увеличиваем минимум, а максимум оставляем тем же. В случае, когда левый или правый сын не удовлетворяет условию дерева поиска, этот узел не включается в искомое поддерево и дальше не рассматривается. Функция возвращает значение переменной <tex>\mathtt{res}</tex>, где записано количество вершин поддерева.  '''int''' dfs(v: '''Node''', max: '''T''', min: '''T''') res = 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

[[Файл:BST_from_seq.gif|right|thumb|260px257px|Восстановление дерева поиска по последовательности ключей]] Как мы помним, процедура <tex>\mathrm{preorderTraversal}</tex> выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем на каком-то моменте делает шаг вправо и снова движется влево. Это продолжается до тех пор, пока не будут выведены все вершины. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения, будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём номер, нарушающий убывающую последовательность, а для каждого такого номера будем искать вершину без правого потомка, хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней элемент с таким номером в качестве правого сына. Когда мы, желая найти такую вершину, встречаем какую-нибудь другую, уже имеющую правого сына, проходим по ветке вправо. Мы имеем на это право, так как если такая вершина стоит, то процедура обхода в ней уже побывала и поворачивала вправо, поэтому спускаться в другую сторону смысла не имеет. Вершину с максимальным ключом, с которой будем начинать поиск, будем запоминать. Она будет обновляться каждый раз, когда появится новый максимум. Процедура восстановления дерева работает за <tex>O(n)</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 2 1 '''''4'' родителем будет узел с числом ''2' <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>.''. Вершины закончились, мы построили дерево.|}

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