Изменения

Рассмотрим, как изменяется количество вершин в дереве после применения к нему операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>. <br>Разобьём все вершины дерева на три группы: * <tex>T_0</tex> {{---}} входящая степень которых равна нулю, одному и больше одного. Обозначим их количество за * <tex>T_0, T_1</tex> и {{---}} входящая степень равна одному,* <tex>T_2</tex> соответственно{{---}} входящая степень больше одного.  

|statement=После применения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> к лесу, математическое ожидание количества вершин в нём не превосходит <tex>\fracdfrac{7}{8}</tex> от их исходного числа.|proof=Математическое ожидание количества удаленных вершин <tex>\mathrm{deleted} = T_0 + \fracdfrac{T_1}{8}</tex> (так как все листья будут удалены после операции <tex>\mathrm{Rake}</tex>, а каждая вершина, у которой ровно один сын, будет удалена с вероятностью <tex>1</tex> после операции <tex>\mathrm{Compress}</tex>). Из предыдущей леммы получаем:<br><tex>\mathrm{deleted} = \fracdfrac{1}{2} (T_0 + T_2) + \fracdfrac{1}{8} T_1 \geqslant \fracdfrac{1}{8} (T_0 + T_1 + T_2)</tex>.