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