Изменения

Перейти к: навигация, поиск

Rake-Compress деревья

46 байт добавлено, 22:49, 10 мая 2016
Нет описания правки
|about=1
|statement=<tex>T_2 \leqslant T_0 - 1</tex>.
|proof=Докажем по индукции по высоте дерева.<br>* '''База *: Для дерева из одной вершины утверждение верно.<br>* '''Переход*: Пусть утверждение доказано для деревьев высоты меньше <tex>h</tex>. Докажем для дерева высоты ровно <tex>h</tex>. Рассмотрим степень корня. <br>Если корень имеет ровно одного ребенка, то переходим к случаю дерева высоты <tex>h - 1</tex>. <br>Если у дерева несколько поддеревьев, то имеем:<br><tex>T_2 = 1 + \sum\limits_{u \in children(root)}T_2(u) \leqslant 1 + \sum\limits_{u \in children(root)}(T_0(u) - 1)</tex>&nbsp;&nbsp;<tex> \leqslant -1 + \sum\limits_{u \in children}T_0(u) \leqslant -1 + T_0 = T_0 - 1</tex>.
Заметим, что для леса деревьев лемма также справедлива.
}}
188
правок

Навигация