Изменения
Нет описания правки
1.<tex> R(L(v))>R(v) </tex>
2. Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида : <tex> v -> \rightarrow L(v) -> \rightarrow L(L(v)) -> \rightarrow ... ->\rightarrow P(v) </tex>
Записав неравенство из первого пункта вдоль пути из второго пункта следует что <tex> R(P(v))>R(v) </tex>
}}
{{Утверждение
|statement=
<tex> R(v)=i => \Rightarrow K(v) \ge 2^i </tex>
|proof=
Докажем по индукции:
Для 0 равенство очевидное.
Ранг вершины стает равным <tex> i </tex> при сливании поддеревьев ранга i-1, отсюда следует:
<tex>K(v)>=\ge K(v1)+K(v2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
}}
Из второго утверждения следует:
1. <tex> R(v)<= \le log_2(n) </tex>
2. Количество вершин ранга <tex> i <= \le {n \over 2^i} </tex>
Обозначим эти классы <tex> T1,T2,T3 </tex>
Амортизированная стоимость <texwikitex>$$S= {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T1} \limits 1} + {\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T3} \limits 1} ) / m $$</texwikitex> , где <tex> {v \in get } </tex> означает что ребро начало которого находится в <tex> v </tex> было пройдено во время выполнения текущего <tex> get </tex>.
Ребро <tex> v </tex> эквивалентно вершине в которой оно начинается.
В результате <tex> S=O(1)+O(log^*(x))+O(1)=O(log^*(x)) </tex>.
В силу того что интервал <tex> (1,4445...2) </tex> не пустой теорема доказана.
}}
* [http://en.wikipedia.org/wiki/Iterated_logarithm Wikipedia -Iterated logarithm]
