Изменения

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

При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить '''этот''' минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <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>\mathrmmathtt{false}</tex>. Если мы дойдём же, дойдя до листьев и , функция не найдём противоречащих условию вершинвстретит на своём пути такие вершины, возвращаем она вернёт значение <tex>\mathrmmathtt{true}</tex>.====Реализация========Псевдокод==== '''bool''' check(v : '''Node''', min: '''integer''', max: '''integer'''): <font color="green">//min и max - минимально и максимально допустимые значения в вершинах поддерева.</font> '''if''' v.left != ''null'' '''if''' v.left.key > v.key '''or''' v.left.key < min '''return''' false '''else''' check(v.left, min, v.key) '''if''' v.right.key < v.key '''or''' v.right.key > max '''return''' false '''else''' check(v.right, v.key, max) '''return''' true

===Поиск максимального поддереваФункция принимает на вход исследуемую вершину, являющегося BSTа также два значения: <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>|definition '''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> {{---}} количество всех вершин, которые могут находиться в таком поддереве снова при помощи [[Обход в глубину, цвета вершин|обхода в глубину]]дереве.

В переменную <tex>maxdp</tex>, изначально равную <tex>-1</tex>, запишем число вершин ===Задачи на поиск максимального поддерева поиска. Будем также вместе с <tex>maxdp</tex> обновлять <tex>maxroot</tex>, где будет храниться корень такого поддерева. Чтобы найти <tex>maxdp</tex>, обойдём вершины и для каждой из них с помощью процедуры <tex>dfs</tex>, на вход которой подаются сама вершина, максимально и минимально возможные элементы поддерева и количество вершин, посчитаем число элементов, принадлежащих максимальному дереву поиска, для которого данная вершина является корнем. Если результат после обхода вершины оказался больше значения BST в переменной <tex>maxdp</tex>, обновляем <tex>maxdp</tex> и <tex>maxroot</tex>. Затем переходим к следующей вершине. После того как мы прошлись по всему дереву, посчитали <tex>maxdp</tex> и нашли <tex>maxroot</tex>, запускаем процедуру <tex>dfsPrint(maxroot, -INF, INF)</tex> для вывода вершин поддерева поиска. До запуска процедуры <tex>dfs</tex> от каждой вершины переменная <tex>dp</tex> равна единице.заданном двоичном дереве===

maxdp {{Задача|definition = -1Найти в данном дереве такую вершину, что она будет корнем поддерева поиска с наибольшим количеством вершин. maxroot = ''null''}} '''for''' u '''in''' Tree Если мы будем приведённым выше способом проверять каждую вершину, мы справимся с задачей за <font color="green"tex>O(n^2)<// Здесь Tree – заданное двоичное деревоtex>.Но её можно решить за <tex>O(n)</fonttex> dp = 1 dfs(u, -INF, INFидя от корня и проверяя все вершины по одному разу, dp)основываясь на следующих фактах: '''if''' dp > maxdp* Значение в вершине больше максимума в её левом поддереве; maxdp = dp* Значение в вершине меньше минимума в её правом поддереве; maxroot = u dfsPrint(maxroot, -INF, INF)* Левое и правое поддерево являются деревьями поиска.

Процедура Введём <tex>dfs(\mathtt{v,max,.min,res)}</tex> позволяет подсчитать максимальное количество вершин двоичного поддерева поиска с вершиной и <tex>\mathtt{v.max}</tex>, которые будут хранить минимум в левом поддереве вершины и максимум в правом. В начале работы этой процедуры Тогда мы должны будем проверить, являются ли эти поддеревья деревьями поиска и, если да, лежит ли ключ вершины <tex>max\mathtt{v}</tex> и между этими значениями <tex>\mathtt{v.min}</tex> принимают нейтральные значения (и <tex>-INF\mathtt{v.max}</tex> и . Если вершина является листом, она автоматически становится деревом поиска, а её ключ {{---}} минимумом или максимумом для её родителя (в зависимости от расположения вершины). Функция <tex>INF\mathtt{cnt}</tex> соответственно, где записывает в <tex>INF\mathtt{v.kol}</tex> - очень большое число)количество вершин в дереве, а если оно является деревом поиска или <tex>res\mathtt{-1}</tex> равен в противном случае. После выполнения функции ищем за линейное время вершину с наибольшим значением <tex>1\mathtt{v.kol}</tex> (одна вершина в дереве уже имеется). Обход осуществляется следующим образом:

'''int'''1 шаг.count(root: '''Node''' Проверяем, есть ли у вершины левый сын. Если его нет, переходим к пункту 2, иначе сравниваем значения в этой вершине и в её левом потомке, а также значение в левом сыне с максимумом в поддереве. Если значение в левом сыне меньше, чем значение в вершине и больше переменной ): <texfont color="green">max</tex>, то запускаем <tex>dfs/ root — корень заданного двоичного дерева.</texfont> из левого сына '''int''' cnt(v: '''Node'''): '''if''' v == ''null'' v.kol = 0 '''return''' = 0 '''if''' cnt(v.left) != -1 '''and''' cnt(v. Здесь роль <tex>right) != -1 '''if''' v.left == ''null'' '''and''' v.right == ''null'' v.min = v.key v.max = v.key v</tex> будет разыгрывать <tex>.kol = 1 '''return''' 1 '''if''' v.left</tex>, <tex>== ''null'' '''if''' v.right.max</tex> приобретёт значение <tex>v.key</tex>, <tex> v.min</tex> по-прежнему останется <tex>= v.key v.kol = cnt(v.right) + 1 '''return''' v.kol '''if''' v.right == ''null'' '''if''' v.left.min</tex>, а <tex>res</tex> увеличится на <tex>v.key v.max = v.key v.kol = cnt(v.left) + 1 '''return''' v.kol '''if''' v.left.min </tex>v. key '''Пояснение:and''' ключи вершин левого поддерева не должны превосходить значения в рассматриваемой вершине, поэтому мы изменяем <tex>v.right.max</tex>v.key v.min = v.left. На <tex>min</tex> эта вершина не влияет в случае левого поддерева, поэтому он не изменяется v.max = v.right.max v.kol = v.left.kol + v.right.kol + 1 v.kol = cnt(v.left) + cnt(v. <tex>res</tex> увеличивается на <tex>right) + 1</tex>, так как в наше поддерево добавилась ещё одна вершина '''return''' v.kol '''return''' -1 '''return''' cnt(root)

'''2 шаг.''' Аналогично действуем с правым потомком. Проверяем его наличие. Если он существует, то сравниваем значение в нём с минимумом и с ключом вершины. Если значение правого сына больше минимума в поддереве и меньше значения в вершине, то запускаем от потомка <tex>dfs</tex>. Теперь на место Алгоритм работает за <tex>v</tex> встаёт <tex>v.rightO(n)</tex>, <tex>max</tex> остаётся прежнимтак как мы прошлись по дереву два раза за время, <tex>min</tex> становится ключом в рассматриваемой вершине, а <tex>res</tex> снова увеличивается на <tex>1</tex>. Для случая с правым поддеревом рассуждения аналогичныравное количеству вершин.

{{Задача|definition = Восстановить дерево по последовательности, выведенной после выполнения процедуры <tex>\mathrm{preorderTraversal}</tex>.}}[[Файл:BST_in_TreeBST_from_seq.gif|centreright|thumb|800px257px|Пример выполнения процедуры dfs для вершины с номером 7Восстановление дерева поиска по последовательности ключей]] Процедура обхода дерева представлена ниже:  '''procedure''' dfs(v: '''Node''', max: '''T''', min: '''T''', res: '''integer''') '''if''' v.left != ''null'' '''if''' v.left.key < v.key '''and''' v.left.key > max dfs(v.left, v.left.key, min, res+1) '''if''' v.right != ''null'' '''if''' v.right.key > v.key '''and''' v.right.key < min dfs(v.left, max, v.left.key, res+1)

НаконецКак мы помним, рассмотрим процедуру процедура <tex>dfsPrint\mathrm{preorderTraversal}</tex>выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, выводящую максимальное дерево поисказатем на каком-то моменте делает шаг вправо и снова движется влево. Так как <tex>maxdp</tex> уже посчитаноЭто продолжается до тех пор, достаточно задать три параметра: корень пока не будут выведены все вершины. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева . Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения, будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём номер, нарушающий убывающую последовательность, а для каждого такого номера будем искать вершину без правого потомка, хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и максимальное подвешиваем к ней элемент с таким номером в качестве правого сына. Когда мы, желая найти такую вершину, встречаем какую-нибудь другую, уже имеющую правого сына, проходим по ветке вправо. Мы имеем на это право, так как если такая вершина стоит, то процедура обхода в ней уже побывала и минимальное допустимые значенияповорачивала вправо, поэтому спускаться в другую сторону смысла не имеет. <tex>max</tex> и <tex>min</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 tex> max dfsPrintO(v.left, v.left.key, minn) '''if''' v.right != ''null'' '''if''' v.right.key </tex> v.key '''and''' v.right.key < min dfsPrint(v.left, max, v.left.key)

Заметим, что Разберём алгоритм на примере последовательности <tex>dfsPrint\mathtt{8}</tex> выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем делает шаг вправо, потом снова влево и так до тех пор, пока не будет выведено <tex>maxdp\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>.''. Итак, мы построили дерево.|}

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