1632
правки
Изменения
м
Время выполнения работы алгоритма {{---}} Алгоритм работает за <tex>O(n)</tex>. {{Задача|definition = Выделить в данном дереве наибольшее возможное количество соседних вершин, образующих дерево поиска.}}Рассмотрим каждую вершину дерева, предполагая, что она может быть корнем максимального поддерева поиска. Найдём для каждой из них количество всех вершин, которые могут находиться в таком поддереве. Максимальный из результатов, получаемых на каждом шаге, будем запоминать. Вместе с максимумом будем запоминать и соответствующую ему вершину. После того, так как мы обошли всё дерево и нашли корень дерева поиска с наибольшим количеством вершин, при помощи обхода <tex>\mathrm{preorderTraversal}</tex> выводим все вершины на экран. '''Node''' root(Tree[n]: '''Node''') maxdp = -1 maxroot = ''null'' '''for''' u '''in''' Tree dp = dfs(u, <tex> -\infty </tex>, <tex> \infty </tex>) '''if''' dp > maxdp maxdp = dp maxroot = u '''return''' maxroot Функция <tex>\mathtt{dfs}</tex> позволяет найти для каждой вершин максимально возможное количество узлов поддерева. На вход функции подаются сама анализируемая вершина и левая и правая границы интервала, в которой могут находиться значения в её поддереве. Начальные значения двух последних аргументов равны <tex> -\infty </tex> и <tex> \infty </tex> соответственно. В основе функции также лежит [[Обход в глубинупрошлись по дереву два раза за время, цвета равное количеству вершин|обход в глубину]]. Рекурсивная функция обходит всех существующих детей вершины, поданной на вход, и, если ребёнок не нарушает условия дерева поиска, она добавляет его в поддерево и анализирует его потомков. В этом случае роль <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>.
* [[АВЛ-дерево]]
rollbackEdits.php mass rollback
=== Поиск следующего и предыдущего элемента ===
====Реализация с использованием информации о родителе====
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним предыдущий ему элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.
'''Node''' next(x : '''Node'''):
'''if''' x.right != ''null''
'''return''' y
Обе операции выполняются за время <tex>O(h)</tex>.
====Реализация без использования информации о родителе====
Рассмотрим поиск следующего элемента для некоторого ключа <tex>x</tex>. Поиск будем начинать с корня дерева, храня текущий узел <tex>current</tex> и узел <tex>successor</tex>, последний посещенный узел, ключ которого больше <tex>x</tex>. <br>
====Рекурсивная реализация====
При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить '''этот''' минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <tex>O(h)</tex>.
Рекурсивная функция, возвращающая дерево с удаленным элементом <tex>z</tex>:
'''Node''' delete(root : '''Node''', z : '''T'''): <font color="green">// корень поддерева, удаляемый ключ</font>
'''else if''' root.left != ''null'' '''and''' root.right != ''null''
root.key = minimum(root.right).key
root.right = delete(root.right, root.right.key)
'''else'''
'''if''' root.left != ''null''
root = root.left
'''else if''' root.right != ''null''
root = root.right
'''else'''
root = root.right''null''
'''return''' root
Функция принимает на вход исследуемую вершину, а также два значения: <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>.
'''functionbool''' lookisBinarySearchTree(Tree[n]root: '''Node''') : <font color="green">// Здесь Tree 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>
Время работы алгоритма {{---}} <tex>O(n)</tex>, где <tex>n</tex> {{---}} количество вершин в дереве.
{{Задача
|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{-\infty 1}</tex> и в противном случае. После выполнения функции ищем за линейное время вершину с наибольшим значением <tex> \infty mathtt{v.kol}</tex>.
'''Nodeint''' maxrootcount(Tree[n]root: '''Node''') : <font color="green">// Tree root — заданное двоичное деревокорень заданного двоичного дерева.</font> '''int''' kolcnt(v: '''Node'''): '''if''' v == ''null'' v.kol = 0 '''return''' = 0 '''if''' kolcnt(v.left) != -1 '''and''' kolcnt(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.max > v.key v.min = v.key v.kol = cnt(v.right) + 1 '''return''' v.kol '''if''' v.right == ''null'' '''if''' v.left.min < v.key v.max = v.key v.kol = cnt(v.left) + 1 '''return''' 1v.kol '''if''' v.left.min < v.key '''and''' v.right.max > v.key v.min = v.left.min v.max = v.right.max '''return''' v.kol = v.left.kol + v.right.kol + 1 v.kol= cnt(v.left) + kolcnt(v.right) + 1 '''elsereturn''' v.kol
'''return''' -1
'''return''' cnt(root)
===Восстановление дерева по результату обхода preorderTraversal===
Разберём алгоритм на примере последовательности <tex>\mathtt{8}</tex> <tex>\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:#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"| ''Зайдя в правое поддерево, процедура обхода снова до упора начала двигаться влево, поэтому действуем аналогичным образом.''
|-
|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>.''
|}
* [[Рандомизированное бинарное дерево поиска]]
* [[Красно-черное дерево]]
==Источники информации==
* [https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0 Википедия {{---}} Двоичное дерево поиска]
