Изменения

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

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

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

root = root.right''null''

'''bool''' check(v : '''Node'''Функция принимает на вход исследуемую вершину, min: '''int''', maxа также два значения: '''int'''): <font color="green"tex>\mathtt{min}<// min tex> и <tex>\mathtt{max — минимально }</tex>, которые до вызова функции равнялись <tex> \infty </tex> и максимально допустимые значения в вершинах поддерева.<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 != ''null'' '''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:Tree_mistakes'''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.png|right|thumb|260px|Пример дерева, для которого недостаточно проверки лишь его соседей]]v.key, max) '''return''' check(root, <tex> -\infty </tex>, <tex> \infty </tex>)

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

===Поиск Задачи на поиск максимального поддерева, являющегося BST, в заданном двоичном дереве===

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

Будем рассматривать Если мы будем приведённым выше способом проверять каждую вершину дерева, предполагая, что она может являться корнем максимального поддерева поиска. Найдём для каждой из них количество всех вершин, которые могут находиться в таком поддереве. Максимальный из результатов, получаемых на каждом шаге, будем запоминать. Вместе с максимумом будем запоминать и соответствующую ему вершину. После того, как мы обошли всё дерево и нашли корень дерева поиска справимся с наибольшим количеством вершин, при помощи обхода задачей за <tex>\mathrm{preorderTraversal}</tex> выводим все вершины на экран.  '''Node''' rootO(n^2) maxdp = -1 maxroot = ''null'' '''for''' u '''in''' Tree <font color="green">// Здесь Tree — заданное двоичное дерево.</font> dp = dfs(u, <tex> -\infty . Но её можно решить за </tex>, <tex> \infty </tex>O(n) '''if''' dp > maxdp maxdp = dp maxroot = u '''return''' maxroot Функция <tex>\mathtt{dfs}</tex> позволяет найти для каждой вершин максимально возможное количество узлов поддерева. На вход функции подаются сама анализируемая вершина , идя от корня и левая и правая границы интервалапроверяя все вершины по одному разу, основываясь на следующих фактах:* Значение в вершине больше максимума в её левом поддереве;* Значение в которой могут находиться значения вершине меньше минимума в её правом поддереве. Начальные значения двух последних аргументов равны <tex> -\infty </tex> ;* Левое и <tex> \infty </tex> соответственноправое поддерево являются деревьями поиска.

В основе функции также лежит [[Обход Введём <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'''): <texfont color="green">\mathtt{res}// root — корень заданного двоичного дерева.</texfont> '''int''' cnt(v: '''Node'''): '''if''' v == ''null'' v.kol = 0 '''return''' = 0 '''if''' cnt(v.left) != -1 '''and''' cnt(v.right) != -1 '''if''' v.left == ''null'' '''and''' v.right == ''null'' v.min = v.key v.max = v.key v.kol = 1 '''return''' 1 '''if''' v.left == ''null'' '''if''' v.right.max >, где записано количество вершин поддереваv.key v.min = v.key v.kol = cnt(v.right) + 1 '''return''' v.kol '''if''' v.right == ''null'' '''if''' v.left.min < v.key v.max = v.key v.kol = cnt(v.left) + 1 '''return''' v.kol '''if''' v.left.min < v.key '''and''' v.right.max > v.key v.min = v.left.min v.max = v.right.max v.kol = v.left.kol + v.right.kol + 1 v.kol = cnt(v.left) + cnt(v.right) + 1 '''return''' v.kol '''return''' -1 '''return''' cnt(root)

'''int''' dfs(v: '''Node''', max: '''T''', min: '''T''') res = 1 '''if''' v.left != ''null'' '''if''' v.left.key Алгоритм работает за < v.key '''and''' v.left.key tex> max res += dfsO(v.left, v.left.key, minn) '''if''' v.right != ''null'' '''if''' v.right.key </tex> v.key '''and''' v.right.key < min res += dfs(v.left, maxтак как мы прошлись по дереву два раза за время, vравное количеству вершин.left.key) '''return''' res

Как мы помним, процедура Разберём алгоритм на примере последовательности <tex>\mathtt{8}</tex> <tex>\mathtt{2}</tex> <tex>\mathrmmathtt{preorderTraversal1}</tex> <tex>\mathtt{4}</tex> <tex>\mathtt{3}</tex> выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем на каком-то моменте делает шаг вправо и снова движется влево. Это продолжается до тех пор, пока не будет выведено <tex>\mathtt{maxdp5}</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>.''. Итак, мы построили дерево.|}

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