243
правки
Изменения
→Задачи на поиск максимального BST в заданном двоичном дереве
Введём <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{-1}</tex> в противном случае. После выполнения функции ищем за линейное время вершину с наибольшим значением <tex>\mathtt{v.kol}</tex>.
'''func''' count(T[n]: '''Node''') <font color="green">// Tree — заданное двоичное дерево.</font> '''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.max > v.key
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''' v.kol '''if''' v.left.min < v.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
'''ifreturn''' v.left.min < v.key '''and''' v.right.max > v.key -1 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.rightroot) + 1 '''return''' v.kol '''return''' -1
Алгоритм работает за <tex>O(n)</tex>, так как мы прошлись по дереву 2 раза за время, равное количеству вершин.
