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