212
правок
Изменения
м
Содержимое страницы заменено на «==В разработке== Триангуляция Делоне на Сфере»
== Двоичное дерево поиска =====Проверка двоичного дерева===Дано произвольное двоичное дерево и необходимо узнать является ли оно деревом поиска. Чтобы дерево было деревом поиска достаточно выполнение следующих условий для всех вершин:* правое и левое поддеревья являются деревьями поиска,* максимум в левом поддереве меньше значения в текущей вершине, а минимум в правом больше. ====Псевдокод====Для удобства опишем класс '''Node'''(вершина). В поле '''max''' будем хранить максимальное значение в данном поддереве, в поле '''min''' минимальное значение, а поля '''l''' и '''r''' хранят ссылки на левого и правого сыновей соответственно. <code> '''boolean''' isSearchTree(Node v): '''if''' (v.l == null && v.r == null) <font color = "green">// Если текущая вершина - лист</font> v.max = v.val; v.min = v.val; '''return''' true; '''if''' (isSearchTree(v.l) && isSearchTree(v.r) && v.l.max < v.val && v.r.min > v.val) v.max = v.r.max; v.min = v.l.min; '''return''' true; '''else''' '''return''' false;</code>===Поиск максимального поддерева, являющегося целым деревом поиска===Под размером дерева будем понимать количество вершин в нем. Тогда, чтобы получить решение модифицируем решение предыдущей задачи. Для каждой вершины так же будем хранить размер поддерева поиска, в котором она является корнем. Тогда получается, что для листьев он равен <tex dpi = 120> 1 </tex>, для всех остальных вершин надо проверить является ли их поддерево деревом поиска. Если да, то размер будет равен сумме размеров поддеревьев сыновей плюс один (т.к. учитываем текущую вершину), иначе <tex dpi = 120> 1 </tex>. ====Псевдокод==разработке== Глобальная переменная '''ans''' хранит ссылку [[Триангуляция Делоне на корень текущего максимально поддерева поиска. <code> '''boolean''' isSearchTree(Node v): '''if''' (v.l == null && v.r == null) <font color = "green">// Если текущая вершина - лист</font> v.max = v.val; v.min = v.val; v.size = 1; '''if''' (1 > currMaxSize) ans = v; currMaxSize = 1; '''return''' true; '''if''' (isSearchTree(v.l) && isSearchTree(v.r) && v.l.max < v.val && v.r.min > v.val) v.max = v.r.max; v.min = v.l.min; v.size = v.l.size + v.r.size + 1; '''if''' (v.size > currMaxSize) ans = v; currMaxSize = v.size; '''return''' true; '''else''' v.size = 1; '''return''' false;</code>Сфере]]
