212
правок
Изменения
м
Содержимое страницы заменено на «==В разработке== Триангуляция Делоне на Сфере»
== Двоичное дерево поиска =====Проверка двоичного дерева на инвариант дерева поиска===Дано произвольное двоичное дерево и необходимо узнать является ли оно деревом поиска. Чтобы дерево было деревом поиска достаточно выполнение следующих условий для всех вершин:* правое и левое поддеревья являются деревьями поиска,* максимум в левом поддереве меньше значения в текущей вершине, а минимум в правом больше. ====Псевдокод====Для решения этой задачи нам понадобятся стандартные функции '''getMax''' и '''getMin''', которые возвращают максимум и минимум в дереве поиска соответственно. <code> '''boolean''' isSearchTree(Node v): '''if''' (v.l == null && v.r == null) <font color = "green">// Если текущая вершина - лист</font> '''return''' true; '''if''' (isSearchTree(v.l) && isSearchTree(v.r) && getMax(v.l) < v.val && getMin(v.r) > v.val) <font color = "green"> // getMax и getMin запускаются только, если оба поддерева являются деревьями поиска </font> '''return''' true; <font color = "green">// Поддерево является деревом поиска</font> '''else''' '''return''' false;</code> ===Поиск максимального целого поддерева, являющегося деревом поиска=В разработке==[[Файл:ЗадачаЦелый.PNG|400px|thumb|right|Ответ Триангуляция Делоне на задачу выделен пунктиромСфере]] Решение этой задачи легко получить из предыдущей. Будем проверять все поддеревья и из тех, что окажутся деревом поиска, выберем максимальное. Под размером дерева подразумевается количество вершин в нем. ====Псевдокод==== Глобальная переменная '''ans''' хранит ссылку на корень текущего максимально поддерева поиска. <code style = "display: inline-block;"> '''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> ===Поиск максимального поддерева, являющегося деревом поиска===В этой задаче нам не требуется найти целое дерево, то есть у любой в таком дереве вершины может не быть одного из поддеревьев. Тогда для решения проверку левого и правого поддеревьев надо сделать отдельно. ====Псевдокод==== <code> '''boolean''' isSearchTree(Node v): v.max = v.val; v.min = v.val; '''boolean''' flag = false; <font color = "green">// true - дерево является деревом поиска, false - нет - лист</font> v.size = 1; '''if''' (v.l == null && v.r == null) <font color = "green">// Если текущая вершина - лист</font> '''if''' (1 > currMaxSize) ans = v; currMaxSize = 1; '''return''' true; '''if''' (isSearchTree(v.l) && v.l.max < v.val) v.min = v.l.min; v.size += v.l.size; flag = true; '''if''' (isSearchTree(v.r) && v.r.min > v.val) v.max = v.r.max; v.size += v.r.size; flag = true; '''if''' (flag && v.size > currMaxSize) ans = v; currMaxSize = v.size; '''if''' (flag) '''return''' true; '''else''' v.size = 1; '''return''' false;</code>
