243
правки
Изменения
→Задачи на поиск максимального BST в заданном двоичном дереве
|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> -\infty </tex> и <tex> \infty </tex>.
'''Node''' maxroot(Tree[n]: '''Node''') <font color="green">// Tree — заданное двоичное дерево.</font>
'''bool''' check2(v: '''Node''')
'''if''' v == ''null''
v.min = <tex> -\infty </tex>
v.max = <tex> \infty </tex>
'''return''' ''true''
'''else'''
v.min = v.left.min
v.max = v.right.max
'''if''' v.min < v.key '''and''' v.max > v.key '''and''' check2(v.left) == ''true'' '''and''' check2(v.right) == ''true''
'''return''' ''true''
Время выполнения работы алгоритма {{---}} <tex>O(n)</tex>.
Рассмотрим каждую вершину дерева, предполагая, что она может быть корнем максимального поддерева поиска. Найдём для каждой из них количество всех вершин, которые могут находиться в таком поддереве. Максимальный из результатов, получаемых на каждом шаге, будем запоминать. Вместе с максимумом будем запоминать и соответствующую ему вершину. После того, как мы обошли всё дерево и нашли корень дерева поиска с наибольшим количеством вершин, при помощи обхода <tex>\mathrm{preorderTraversal}</tex> выводим все вершины на экран.
'''Node''' root(Tree[n]: '''Node''')
maxdp = -1
maxroot = ''null''
'''for''' u '''in''' Tree <font color="green">// Здесь Tree — заданное двоичное дерево.</font>
dp = dfs(u, <tex> -\infty </tex>, <tex> \infty </tex>)
'''if''' dp > maxdp
