Изменения

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

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

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

root = root.right''null''

'''functionbool''' lookisBinarySearchTree(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) '''if''' v.right != ''null'' '''if''' v.right.key < v.key '''or''' v.right.key > max '''return''' ''false'' '''else''' '''returnand''' check(v.right, v.key, max) '''return''' ''true''

'''return''' check(root, <tex> -\infty </tex>, <tex> -\infty </tex>) <font color="green">// root - корень дерева.</font>

|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'''): maxdp '''if''' v == ''null'' v.kol = 0 '''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.</font>key dp v.kol = dfscnt(u, <tex> -\infty </tex>, <tex> \infty </tex>v.right)+ 1 '''return''' v.kol '''if''' v.right == ''null'' '''if''' dp > maxdpv.left.min < v.key maxdp v.max = dpv.key maxroot v.kol = ucnt(v.left) + 1 '''return''' maxrootv.kol Функция '''if''' v.left.min <texv.key '''and''' v.right.max >\mathtt{dfs}</tex> позволяет найти для каждой вершин максимально возможное количество узлов поддерева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. Начальные значения двух последних аргументов равны <tex> kol '''return''' -\infty </tex> и <tex> \infty </tex> соответственно.1 '''return''' cnt(root)

В основе функции также лежит [[Обход в глубину, цвета вершин|обход в глубину]]. Рекурсивная функция обходит всех существующих детей вершины, поданной на вход, и, если ребёнок не нарушает условия дерева поиска, она добавляет его в поддерево и анализирует его потомков. В этом случае роль <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 Время работы алгоритма {{---}} Алгоритм работает за <tex>O(n^2)</tex>, так как мы прошлись по дереву два раза за время, равное количеству вершин.

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

Будем выделять красным цветом вершины, рассматриваемые на каждом шаге, чёрным жирным {{---}} их родителей, курсивом {{---}} убывающие подпоследовательности (в случаях, когда мы их рассматриваем) или претендентов на добавление к ним правого ребёнка (когда рассматривается вершина, нарушающая убывающую последовательность).

|style="background-color:#FFF;padding:2px 10px"| '''''8''''' <span style="color:red">'''''2'''''</span> ''1 '' 4 3 5

| 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''''' <span style="color:red">'''4 ''3'''''</span> 5|style="background-color:#FFF;padding:2px 10px"| Находим убывающую подпоследовательность. Каждую вершину подвешиваем к последней из взятых ранее в качестве левого сына.|style="background-color:#FFF;padding:2px 10px"| Находим первый минимальный элемент {{---}} '''1'Зайдя в правое поддерево, процедура обхода снова до упора начала двигаться влево, поэтому действуем аналогичным образом.''

|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}} '''1'</tex>.''

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