243
правки
Изменения
→Задачи на поиск максимального BST в заданном двоичном дереве
* Левое и правое поддерево являются деревьями поиска.
Введём <tex>\mathtt{v.min}</tex> и <tex>\mathtt{v.max}</tex>, которые будут хранить минимум в левом поддереве вершины и максимум в правом. Тогда мы должны будем проверить, являются ли эти поддеревья деревьями поиска и, если да, лежит ли ключ вершины <tex>\mathtt{v}</tex> между этими значениями и являются ли поддеревья деревьями поиска. Для пустых вершин минимум и максимум равны <tex> -\infty mathtt{v.min}</tex> и <tex> \infty mathtt{v.max}</tex>. Если вершина является листом, она автоматически становится деревом поиска.
'''int''' kol(v: '''Node''')
'''return''' 0
'''if''' kol(v.left) != -1 '''and''' kol(v.right) != -1
'''if''' v.left == ''null'' '''if''' v.right.max > v.key v.min = v.key '''return''' kol(v.right) + 1 '''andif''' v.right == ''null'' '''if''' v.left.min = < v.key v.max = v.key '''return''' kol(v.left) + 1
'''if''' v.left.min < v.key '''and''' v.right.max > v.key
v.min = v.left.min
