Обсуждение участника:Novik — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Содержимое страницы заменено на «==В разработке== Триангуляция Делоне на Сфере»)
 
(не показаны 4 промежуточные версии этого же участника)
Строка 1: Строка 1:
== Двоичное дерево поиска ==
+
==В разработке==
===Проверка двоичного дерева===
+
[[Триангуляция Делоне на Сфере]]
Дано произвольное двоичное дерево и необходимо узнать является ли оно деревом поиска. Чтобы дерево было деревом поиска достаточно выполнение следующих условий для всех вершин:
 
* правое и левое поддеревья являются деревьями поиска,
 
* максимум в левом поддереве меньше значения в текущей вершине, а минимум в правом больше.
 
 
 
====Псевдокод====
 
Для удобства опишем класс '''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>
 
===Поиск максимального поддерева, являющегося деревом поиска===
 
В этой задаче нам не требуется найти целое дерево, то есть у любой в таком дереве вершины может не быть одного из поддеревьев. Тогда для решения проверку левого и правого поддеревьев надо сделать отдельно.
 
 
 
====Псевдокод====
 
 
 
<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>
 

Текущая версия на 17:54, 19 ноября 2016