243
правки
Изменения
→Поиск максимального поддерева, являющегося BST, в заданном двоичном дереве
|definition = Найти в данном дереве максимальное из поддеревьев поиска.
}}
Будем рассматривать каждую вершину дерева, предполагая, что она может являться корнем максимального поддерева поиска. Найдём для каждой из них количество всех вершин, которые могут находиться в таком поддереве снова при помощи [[Обход в глубину, цвета вершин|обхода в глубину]].
В переменную <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> равна единице.
