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