80
правок
Изменения
м
Рассмотрим Возьмем вершину в дереве с <tex>n + 1</tex> листами, у которой два ребенка - листья.Рассмотрим возможные случаи:
→Количество вершин
'''Переход''' <tex>n \rightarrow n + 1</tex>
1) У нее более двух детей. Тогда отрежем от нее лист. Получим дерево с <tex>n</tex> листьями, причем в нем количество внутренних вершин такое же, как в исходном дереве. Но у полученного дерева менее <tex>n</tex> внутренних вершин (т.к. по индукционному предположению для него выполняется условие леммы), значит, для исходного дерева лемма верна.
2) У нее ровно два ребенка. Отрежем их, получим дерево с <tex>n</tex> листьями, количество внутренних вершин которого на <tex>1</tex> меньше, чем в исходном дереве. Тогда, по индукционному предположению, у него менее <tex>n</tex> внутренних вершин, значит , в исходном дереве их меньше <tex>n + 1</tex>.
}}
