70
правок
Изменения
→Количество внутренних вершин
==Количество внутренних вершин==
{{Лемма
|statement=
Количество внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше количества листьев
|proof=
Докажем лемму индукцией по количеству листьев <tex>n</tex>.
''База''
При <tex>n = 2</tex> в дереве одна внутренняя вершина - верно.
''Переход'' <tex>n \rightarrow n + 1</tex>
Рассмотрим все вершины, у которых хотя бы один из детей - лист.
Если среди них есть вершина, у которой более двух детей, отрежем от нее лист. Получим дерево с <tex>n</tex> листьями, удовлетворяющее условию леммы, в котором количество внутренних вершин равно количеству внутренних вершин в исходном дереве. Тогда, по индукционному предположению, у полученного дерева менее <tex>n</tex> внутренних вершин, значит в исходном дереве количество внутренних вершин меньше количества листьев.
Иначе среди этих вершин есть вершина, у которой оба ребенка - листья. Отрежем оба этих листа, получим дерево с <tex>n</tex> листьями, удовлетворяющее условию леммы, количество внутренних вершин которого на <tex>1</tex> меньше количества внутренних вершин в исходном дереве. Тогда, по индукционному предположению, у полученного дерева менее <tex>n</tex> внутренних вершин, значит в исходном дереве количество внутренних вершин меньше <tex>n + 1</tex>.
}}
Так как суффиксное дерево удовлетворяет условиям леммы, то количество внутренних вершин в нем меньше количества листьев, то есть меньше длины строки.
==Хранение в памяти==
