Изменения

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

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

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

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

root = root.right''null''

==Поиск максимального поддерева, являющегося BST, в заданном двоичном Задачи о бинарном деревепоиска==В переменную <tex>maxdp</tex>, изначально равную <tex>-1</tex>, запишем число вершин максимального поддерева поиска. Будем также вместе с <tex>maxdp</tex> обновлять <tex>maxroot</tex>, где будет храниться корень такого поддерева. Чтобы найти <tex>maxdp</tex>, обойдём вершины и для каждой из них с помощью процедуры <tex>dfs</tex>, на вход которой подаются сама вершина, максимально и минимально возможные элементы поддерева и количество вершин, посчитаем число элементов, принадлежащих максимальному дереву поиска, для которого данная вершина является корнем. Если результат после обхода вершины оказался больше значения в переменной <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 = -1 maxroot = ''null'' '''for''' u '''in''' Tree <font color="green">// Здесь Tree – Проверка того, что заданное двоичное дерево.</font> dp является деревом поиска= 1 dfs(u, -INF, INF, dp) '''if'''(dp>maxdp) maxdp = dp maxroot = u dfsPrint(maxroot,-INF,INF)

Функция <tex>dfs(v{{Задача|definition = Определить, является ли заданное двоичное дерево деревом поиска.}}[[Файл:Not_Enough.png|right|thumb|291px|Пример дерева,maxдля которого недостаточно проверки лишь его соседних вершин]]Для того чтобы решить эту задачу,minприменим [[Обход в глубину,res)</tex> возвращает максимальное количество цвета вершин двоичного поддерева поиска с вершиной <tex>v</tex>|обход в глубину]]. В начале работы этой функции Запустим от корня рекурсивную логическую функцию, которая выведет <tex>max\mathtt{true}</tex> , если дерево является BST и <tex>min</tex> принимают нейтральные значения (<tex>-INF\mathtt{false}</tex> в противном случае. Чтобы дерево не являлось BST, в нём должна быть хотя бы одна вершина, которая не попадает под определение дерева поиска. То есть достаточно найти всего одну такую вершину, чтобы выйти из рекурсии и вернуть значение <tex>INF\mathtt{false}</tex> соответственно. Если же, дойдя до листьев, где <tex>INF</tex> - очень большое число)функция не встретит на своём пути такие вершины, а <tex>res</tex> равен она вернёт значение <tex>1\mathtt{true}</tex> (одна вершина в дереве уже имеется). Обход осуществляется следующим образом:

'''1 шаг.''' Проверяем, есть ли у вершины левый сын. Если его нет, переходим к пункту 2, иначе сравниваем значения в этой вершине и в её левом потомкеФункция принимает на вход исследуемую вершину, а также значение в левом сыне с максимумом в поддереве. Если значение в левом сыне меньше, чем значение в вершине и больше переменной два значения: <tex>max\mathtt{min}</tex>, то запускаем и <tex>dfs</tex> из левого сына. Здесь роль v будет разыгрывать <tex>v.left\mathtt{max}</tex>, которые до вызова функции равнялись <tex>max\infty </tex> приобретёт значение и <tex>v.key-\infty </tex>соответственно, где <tex>min\infty </tex> — очень большое число, т.е. ни один ключ дерева не превосходит его по-прежнему останется <tex>min</tex>модулю. Казалось бы, два последних параметра не нужны. Но без них программа может выдать неверный ответ, а <tex>res</tex> увеличится на 1так как сравнения только вершины и её детей недостаточно. ''Пояснение:'' ключи вершин левого поддерева не должны превосходить значения Необходимо также помнить, в рассматриваемой вершинекаком поддереве для более старших предков мы находимся. Например, поэтому мы изменяем в этом дереве вершина с номером <tex>max8</tex>. На находится левее вершины, в которой лежит <tex>min5</tex> эта вершина , чего не влияет должно быть в случае левого поддеревадереве поиска, поэтому он не изменяется. однако после проверки функция бы вернула <tex>res\mathtt{true}</tex> увеличивается на 1, так как в наше поддерево добавилась ещё одна вершина.

'''2 шагbool''' isBinarySearchTree(root: '''Node'''): <font color="green">// Здесь root — корень заданного двоичного дерева.</font> '''bool''' check(v : '''Node''', min: '''T''' Аналогично действуем с правым потомком. Проверяем его наличие. Если он существует, то сравниваем значение в нём с минимумом max: '''T'''): <font color="green">// min и с ключом вершины. Если значение правого сына больше минимума в поддереве max — минимально и меньше максимально допустимые значения в вершине, то запускаем от потомка <tex>dfsвершинах поддерева.</texfont> '''if''' v == ''null'' '''return''' ''true'' '''if''' v. Теперь на место key <= min '''or''' max <tex>= v.key '''return''' ''false'' '''return''' check(v.left, min, v</tex> встаёт <tex>.key) '''and''' check(v.right</tex>, <tex>v.key, max</tex> остаётся прежним) '''return''' check(root, <tex>min-\infty </tex> становится ключом в рассматриваемой вершине, а <tex>res\infty </tex> снова увеличивается на 1. Для случая с правым поддеревом рассуждения аналогичны.)

'''3 шаг.''' Возвращаем результат в переменной Время работы алгоритма {{---}} <tex>resO(n)</tex>, где записано <tex>n</tex> {{---}} количество вершин поддеревав дереве.

Процедура обхода дерева представлена ниже{{Задача|definition = Найти в данном дереве такую вершину, что она будет корнем поддерева поиска с наибольшим количеством вершин.}}Если мы будем приведённым выше способом проверять каждую вершину, мы справимся с задачей за <tex>O(n^2)</tex>. Но её можно решить за <tex>O(n)</tex>, идя от корня и проверяя все вершины по одному разу, основываясь на следующих фактах:* Значение в вершине больше максимума в её левом поддереве;* Значение в вершине меньше минимума в её правом поддереве;* Левое и правое поддерево являются деревьями поиска.

'''procedure''' dfs(Введём <tex>\mathtt{v: '''Node''', max: '''T''', .min: '''T''', res: '''integer''') '''if''' }</tex> и <tex>\mathtt{v.left != ''null'' '''if''' vmax}</tex>, которые будут хранить минимум в левом поддереве вершины и максимум в правом.left.key Тогда мы должны будем проверить, являются ли эти поддеревья деревьями поиска и, если да, лежит ли ключ вершины < tex>\mathtt{v.key '''and''' }</tex> между этими значениями <tex>\mathtt{v.left.key min}</tex> и <tex> max dfs(\mathtt{v.left, vmax}</tex>.left.key Если вершина является листом, minона автоматически становится деревом поиска, res+1а её ключ {{---}} минимумом или максимумом для её родителя (в зависимости от расположения вершины) '''if''' v.right != ''null'' '''if''' Функция <tex>\mathtt{cnt}</tex> записывает в <tex>\mathtt{v.rightkol}</tex> количество вершин в дереве, если оно является деревом поиска или <tex>\mathtt{-1}</tex> в противном случае.key После выполнения функции ищем за линейное время вершину с наибольшим значением <tex> \mathtt{v.key '''and''' v.right.key kol}< min dfs(v/tex>.left, max, v.left.key, res+1)

Наконец, рассмотрим процедуру '''int''' count(root: '''Node'''): <texfont color="green">dfsPrint</tex>, выводящую максимальное дерево поиска/ root — корень заданного двоичного дерева. Так как <tex>maxdp</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. <tex>max</tex> и v.key v.min = v.key v.kol = cnt(v.right) + 1 '''return''' v.kol '''if''' v.right == ''null'' '''if''' v.left.min <tex>v.key v.max = v.key v.kol = cnt(v.left) + 1 '''return''' v.kol '''if''' v.left.min</texv.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)

'''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 '''print''' v.left.key dfsO(v.left, v.left.key, minn) '''if''' v.right != ''null'' '''if''' v.right.key </tex> v.key '''and''' v.right.key < min '''print''' v.right.key dfs(v.left, maxтак как мы прошлись по дереву два раза за время, v.leftравное количеству вершин.key)

[[Файл:BST_from_sequence.gif|right|===Восстановление дерева поиска по последовательности ключей]]результату обхода preorderTraversal===

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

Как мы помним, процедура <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''. Сначала в корень записывается ''8''. Затем его левым сыном становится вершина с номером ''2'', а её левым сыном - ''1''. Следующее значение - ''4'' - уже нарушает убывающую подпоследовательность. Подберём для него вершину, где лежит значение, меньшее его, причём такая вершина максимальна (в противном случае он будет превосходить и прародителя, находясь в его левом поддереве, а это противоречит определению дерева поиска). Это узел с числом ''2''. Сделаем его правым сыном рассматриваемую вершину. Затем снова дадим левых потомков последней добавленной вершине, опять же, пока не найдём ключ, нарушающий порядок убывания. В нашем случае в дерево дописывается ''3''. Для следующего значения снова ищем родителя, для которого он станет правым сыном. Это значение равно ''4''. Добавляем ''5'' как правого сына для вершины ''4''. Итак, мы построили дерево}</tex>.

Будем выделять красным цветом вершины, рассматриваемые на каждом шаге, чёрным жирным {{---}} их родителей, курсивом {{---}} убывающие подпоследовательности (в случаях, когда мы их рассматриваем) или претендентов на добавление к ним правого ребёнка (когда рассматривается вершина, нарушающая убывающую последовательность).{| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| Состояние последовательности!style="background-color:#EEE"| Действие!style="background-color:#EEE"| Пояснение|-|style=Проверка BST"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>dfs\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">'''''3'''''</span> 5|style="background-color:#FFF;padding:2px 10px"| Находим убывающую подпоследовательность. Каждую вершину подвешиваем к последней из взятых ранее в качестве левого сына.|style="даbackground-color:#FFF;padding:2px 10px"| ''Зайдя в правое поддерево, процедура обхода снова до упора начала двигаться влево, иначе – поэтому действуем аналогичным образом.''|-|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>.'' |}

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