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