Обсуждение участника:Novik — различия между версиями
Novik (обсуждение | вклад) |
Novik (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
'''return''' false; | '''return''' false; | ||
</code> | </code> | ||
| − | ===Поиск максимального поддерева, являющегося | + | ===Поиск максимального целого поддерева, являющегося деревом поиска=== |
Под размером дерева будем понимать количество вершин в нем. Тогда, чтобы получить решение модифицируем решение предыдущей задачи. Для каждой вершины так же будем хранить размер поддерева поиска, в котором она является корнем. Тогда получается, что для листьев он равен <tex dpi = 120> 1 </tex>, для всех остальных вершин надо проверить является ли их поддерево деревом поиска. Если да, то размер будет равен сумме размеров поддеревьев сыновей плюс один (т.к. учитываем текущую вершину), иначе <tex dpi = 120> 1 </tex>. | Под размером дерева будем понимать количество вершин в нем. Тогда, чтобы получить решение модифицируем решение предыдущей задачи. Для каждой вершины так же будем хранить размер поддерева поиска, в котором она является корнем. Тогда получается, что для листьев он равен <tex dpi = 120> 1 </tex>, для всех остальных вершин надо проверить является ли их поддерево деревом поиска. Если да, то размер будет равен сумме размеров поддеревьев сыновей плюс один (т.к. учитываем текущую вершину), иначе <tex dpi = 120> 1 </tex>. | ||
| Строка 44: | Строка 44: | ||
ans = v; | ans = v; | ||
currMaxSize = v.size; | 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; | '''return''' true; | ||
'''else''' | '''else''' | ||
Версия 21:06, 24 мая 2015
Содержание
Двоичное дерево поиска
Проверка двоичного дерева
Дано произвольное двоичное дерево и необходимо узнать является ли оно деревом поиска. Чтобы дерево было деревом поиска достаточно выполнение следующих условий для всех вершин:
- правое и левое поддеревья являются деревьями поиска,
- максимум в левом поддереве меньше значения в текущей вершине, а минимум в правом больше.
Псевдокод
Для удобства опишем класс Node(вершина). В поле max будем хранить максимальное значение в данном поддереве, в поле min минимальное значение, а поля l и r хранят ссылки на левого и правого сыновей соответственно.
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;
Поиск максимального целого поддерева, являющегося деревом поиска
Под размером дерева будем понимать количество вершин в нем. Тогда, чтобы получить решение модифицируем решение предыдущей задачи. Для каждой вершины так же будем хранить размер поддерева поиска, в котором она является корнем. Тогда получается, что для листьев он равен , для всех остальных вершин надо проверить является ли их поддерево деревом поиска. Если да, то размер будет равен сумме размеров поддеревьев сыновей плюс один (т.к. учитываем текущую вершину), иначе .
Псевдокод
Глобальная переменная ans хранит ссылку на корень текущего максимально поддерева поиска.
boolean isSearchTree(Node v):
if (v.l == null && v.r == null) // Если текущая вершина - лист
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;
Поиск максимального поддерева, являющегося деревом поиска
В этой задаче нам не требуется найти целое дерево, то есть у любой в таком дереве вершины может не быть одного из поддеревьев. Тогда для решения проверку левого и правого поддеревьев надо сделать отдельно.
Псевдокод
boolean isSearchTree(Node v):
v.max = v.val;
v.min = v.val;
boolean flag = false; // true - дерево является деревом поиска, false - нет - лист
v.size = 1;
if (v.l == null && v.r == null) // Если текущая вершина - лист
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;
