Изменения

Для того чтобы решить эту задачу, применим [[Обход в глубину, цвета вершин|обход в глубину]]. Начнём путь от корня и будем рассматривать для каждой вершины её детей. Если ребёнок не нарушает условия дерева поиска, спускаемся на следующий уровень. Если же нашлась вершина, стоящая не на своём месте, то этого достаточно, чтобы сказать, что заданное дерево не является деревом поиска, и вернуть значение <tex>\mathrm{false}</tex>. Если мы дойдём до листьев и не найдём противоречащих условию вершин, возвращаем значение <tex>\mathrm{true}</tex>.====Реализация========Псевдокод====

Функция <tex>\mathtt{dfs}</tex> позволяет найти для каждой вершин максимально возможное количество узлов поддерева. На вход функции подаются сама анализируемая вершина и левая и правая границы интервала, в которой могут находиться значения в её поддереве. Начальные значения двух последних аргументов равны <tex>\mathrm{-INF}</tex> и <tex>\mathrm{INF}</tex> соответственно, где <tex>\mathrm{INF}</tex> - очень большое число, т.е. ни один ключ дерева не превосходит его по модулю. В основе функции также лежит [[Обход в глубину, цвета вершин|обход в глубину]]. Рекурсивная функция обходит всех существующих детей вершины, поданной на вход, и, если ребёнок не нарушает условия дерева поиска, она добавляет его в поддерево и анализирует его потомков. Если же левый или правый сын не удовлетворяет условию дерева поиска, он не включается в искомое поддерево и рассматривать его дальше смысла не имеет. '''1 шаг.''' Проверяем, есть ли у вершины левый сын. Если его нет, переходим к пункту 2, иначе сравниваем значения в этой вершине и в её левом потомке, а также значение в левом сыне с максимумом в поддереве. Если значение в левом сыне меньше, чем значение в вершине и больше переменной <tex>max</tex>, то запускаем <tex>dfs</tex> из левого сына. Здесь роль <tex>v</tex> будет разыгрывать <tex>v.left</tex>, <tex>max</tex> приобретёт значение <tex>v.key</tex>, <tex>min</tex> по-прежнему останется <tex>min</tex>, а <tex>res</tex> увеличится на <tex>1</tex>. ''Пояснение:'' ключи вершин левого поддерева не должны превосходить значения в рассматриваемой вершине, поэтому мы изменяем <tex>max</tex>. На <tex>min</tex> эта вершина не влияет в случае левого поддерева, поэтому он не изменяется. <tex>res</tex> увеличивается на <tex>1</tex>, так как в наше поддерево добавилась ещё одна вершина. '''2 шаг.''' Аналогично действуем с правым потомком. Проверяем его наличие. Если он существует, то сравниваем значение в нём с минимумом и с ключом вершины. Если значение правого сына больше минимума в поддереве и меньше значения в вершине, то запускаем от потомка <tex>dfs</tex>. Теперь на место <tex>v</tex> встаёт <tex>v.right</tex>, <tex>max</tex> остаётся прежним, <tex>min</tex> становится ключом в рассматриваемой вершине, а <tex>res</tex> снова увеличивается на <tex>1</tex>. Для случая с правым поддеревом рассуждения аналогичны. '''3 шаг.''' Возвращаем результат в переменной <tex>res</tex>, где записано количество вершин поддерева.

В основе функции также лежит [[Файл:BST_in_Tree.gif|centre|thumb|800pxОбход в глубину, цвета вершин|Пример выполнения процедуры dfs для вершины с номером 7обход в глубину]]. Рекурсивная функция обходит всех существующих детей вершины, поданной на вход, и, если ребёнок не нарушает условия дерева поиска, она добавляет его в поддерево и анализирует его потомков. В этом случае роль <tex>\mathtt{v}</tex> будет разыгрывать ребёнок, удовлетворяющий условию дерева поиска. Если он был левым сыном, то максимально возможному значению присваивается число, стоящее в его родителе, а минимальное возможное значение не изменяется. Наоборот, если он был правым сыном, увеличиваем минимум, а максимум оставляем тем же. В случае, когда левый или правый сын не удовлетворяет условию дерева поиска, этот узел не включается в искомое поддерево и дальше не рассматривается.

'''procedureint''' dfs(v: '''Node''', max: '''T''', min: '''T''', res: '''integer''')