212
правок
Изменения
м
Содержимое страницы заменено на «==В разработке== Триангуляция Делоне на Сфере»
== Двоичное дерево поиска В разработке== ==Проверка двоичного дерева==Дано произвольное двоичное дерево и необходимо узнать является ли оно деревом поиска. Чтобы дерево было деревом поиска достаточно выполнение следующих условий для всех вершин:* правое и левое поддеревья являются деревьями поиска,* максимум в левом поддереве меньше значения в текущей вершине, а минимум в правом больше. Псевдокод: <code> '''boolean''' isSearchTree(Node v): if (v.l == null && v.r == null) 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>==Поиск максимального поддерева, являющегося целым деревом поиска==Под размером дерева будем понимать количество вершин в нем. Тогда, чтобы получить решение модифицируем решение предыдущей задачи. Для каждой вершины так же будем хранить размер поддерева поиска, в котором она является корнем.[[Триангуляция Делоне на Сфере]]
