Изменения

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

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