Изменения

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

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

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

root = root.right''null''

'''bool''' check(v : '''Node'''Функция принимает на вход исследуемую вершину, min: '''integer''', maxа также два значения: '''integer'''): <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: '''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>-\mathtt{min}infty </tex> и , <tex>\mathtt{max}infty </tex>, которые до вызова функции равнялись -бесконечности и +бесконечности. Казалось бы, два последних параметра не нужны. Но без них программа может выдать неверный ответ, так как сравнения только вершины и её детей недостаточно. Необходимо также помнить, в каком поддереве для более старших предков мы находимся.)

Время работы алгоритма {{---}} <tex>O(n)</tex>, где <tex>n</tex> {{---}} количество вершин в дереве. ===Поиск Задачи на поиск максимального поддерева, являющегося BST, в заданном двоичном дереве===

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

Будем рассматривать Если мы будем приведённым выше способом проверять каждую вершину дерева, предполагаямы справимся с задачей за <tex>O(n^2)</tex>. Но её можно решить за <tex>O(n)</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>\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> \infty </tex> — очень большое число, т.е. ни один ключ дерева не превосходит его по модулюравное количеству вершин.

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

Функция возвращает значение переменной {{Задача|definition = Восстановить дерево по последовательности, выведенной после выполнения процедуры <tex>\mathttmathrm{respreorderTraversal}</tex>, где записано количество вершин поддерева.}}[[Файл:BST_from_seq.gif|right|thumb|257px|Восстановление дерева поиска по последовательности ключей]]

'''int''' dfs(v: '''Node'''Как мы помним, maxпроцедура <tex>\mathrm{preorderTraversal}</tex> выводит значения в узлах поддерева следующим образом: '''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

===Восстановление Процедура восстановления дерева по результату обхода preorderTraversal===работает за <tex>O(n)</tex>.

Как мы помним, процедура Разберём алгоритм на примере последовательности <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>.''. Итак, мы построили дерево.|}

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