Изменения
Нет описания правки
Пусть <tex> union(v1,v2) </tex> - процедура слития двух множеств содержащих <tex> v1</tex>,<tex> v2</tex>, а <tex> get(v) </tex> - поиск корня поддерева содержащего x<tex> v </tex>. Рассмотрим <tex> n </tex> операций <tex> union </tex> и <tex> m </tex> операций <tex> get</tex>. Для удобства и без потери общности будем считать что у нас <tex> union </tex> принимает в качестве аргументов корни поддеревьев и (<tex> m>n)</tex>, то есть (<tex> union(v1,v2) </tex> заменяем на <tex> union(get(v1),get(v2))</tex>. Тогда нам надо оценить стоимость операции <tex> get(v)</tex>. Обозначим <tex>R(v)</tex> - ранг вершины,<tex>P(v)</tex> - отец вершины,<tex>L(v) </tex> - самый первый отец вершины. , <tex> K(v) </tex> - количество вершин в поддерева корнем которого является <tex> v </tex>
{{Утверждение
Из того как работает функция get следует:
1.<tex> R(L(v))>R(v) </tex>
2. Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида : <tex> v -> L(v) -> L(L(v)) ... ->P(v) </tex>
Записав неравенство из первого пункта вдоль пути из второго пункта следует что <tex> R(P(v))>R(v) </tex>
}}
{{Утверждение
|statement=
<tex> R(v)=i => K(v) >=2^i </tex>
|proof=
Докажем по индукции:
Для 0 равенство очевидное.
Ранг вершины стает равным <tex> i </tex> при сливании поддеревьев ранга i-1, отсюда следует:
<tex>K(v)>=K(v1)+K(v2)>=2^(i-1)+2^(i-1)>=2^i </tex>.
}}
