243
правки
Изменения
→Поиск максимального поддерева, являющегося BST, в заданном двоичном дереве
maxroot = ''null''
'''for''' u '''in''' Tree <font color="green">// Здесь Tree – заданное двоичное дерево.</font>
dp = dfs(u, <tex> -INF\infty </tex>, INF<tex> \infty </tex>)
'''if''' dp > maxdp
maxdp = dp
'''return''' maxroot
Функция <tex>\mathtt{dfs}</tex> позволяет найти для каждой вершин максимально возможное количество узлов поддерева. На вход функции подаются сама анализируемая вершина и левая и правая границы интервала, в которой могут находиться значения в её поддереве. Начальные значения двух последних аргументов равны <tex>-\mathrm{-INF}infty </tex> и <tex>\mathrm{INF}infty </tex> соответственно, где <tex>\mathrm{INF}infty </tex> - очень большое число, т.е. ни один ключ дерева не превосходит его по модулю.
В основе функции также лежит [[Обход в глубину, цвета вершин|обход в глубину]]. Рекурсивная функция обходит всех существующих детей вершины, поданной на вход, и, если ребёнок не нарушает условия дерева поиска, она добавляет его в поддерево и анализирует его потомков. В этом случае роль <tex>\mathtt{v}</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, res+1)
'''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+1)
Наконец, рассмотрим процедуру <tex>dfsPrint</tex>, выводящую максимальное дерево поиска. Так как <tex>maxdp</tex> уже посчитано, достаточно задать три параметра: корень поддерева и максимальное и минимальное допустимые значения. <tex>max</tex> и <tex>min</tex> нам понадобятся, чтобы взять только те вершины, которые принадлежат дереву.
