13
правок
Изменения
Нет описания правки
|proof=
Из принципа работы функции <tex> get </tex> следует:
#<tex> R(L(v))>R(v) </tex>.#Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>.
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}
Из последнего утверждения следует:
#<tex> R(v) \le \log_2(n) </tex>.#Количество вершин ранга <tex> i \le {n \over 2^i} </tex>.
{{Теорема
