1302
правки
Изменения
м
Нет описания правки
Оценим стоимость операции <tex> get(v) </tex>.
Обозначим <tex>R(v)</tex> — ранг вершины, <tex>P(v)</tex> — отец вершиныпредставитель множества, содержащего <tex> v </tex>, <tex>L(v) </tex> — самый первый отец вершины,<tex> K(v) </tex> — количество вершин в поддереваподдереве, корнем которого является <tex> v </tex> .
{{Утверждение
Для 0 равенство очевидно.
Ранг вершины стает равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, отсюда следуетследовательно:
<tex>K(v) \ge K(v_1) + K(v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.
}}
Из второго последнего утверждения следует:
#<tex> R(v) \le \log_2(n) </tex>
#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>
#Все остальные.
