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