313
правок
Изменения
→Количество вершин
<br/>
==Количество Число вершин==По определению, в суффиксном дереве содержится <tex>n</tex> листьев. Оценим количество число внутренних вершин такого дерева.
{{Лемма
|statement=
|proof=
Докажем лемму индукцией по количеству числу листьев <tex>n</tex>.
'''База'''
Возьмем вершину в дереве с <tex>n + 1</tex> листами, у которой два ребенка {{---}} листья. Рассмотрим возможные случаи:
# У нее более двух детей. Тогда отрежем от нее лист. Получим дерево с <tex>n</tex> листьями, причем в нем количество число внутренних вершин такое же, как в исходном дереве. Но у полученного дерева по индукционному предположению менее <tex>n</tex> внутренних вершин, а, значит, и для исходного дерева лемма верна.# У нее ровно два ребенка. Отрежем их, получим дерево с <tex>n - 1</tex> листьями, количество число внутренних вершин которого на <tex>1</tex> меньше, чем в исходном дереве. Тогда по индукционному предположению у него менее <tex>n - 1</tex> внутренних вершин, значит, в исходном дереве их меньше <tex>n</tex>.
}}
