Изменения

Введём <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>.

'''int''' kolcnt(v: '''Node''')

'''return''' v.kol = 0 '''if''' kol(v.left) .kol != -1 '''and''' kol(v.right) .kol != -1

'''return''' v.kol = 1

'''return''' v.kol(= v.right) .kol + 1

'''return''' v.kol(= v.left) .kol + 1

'''return''' v.kol(= v.left) .kol + kol(v.right) .kol + 1 '''returnelse''' v.kol = -1