Изменения

Без использования дополнительных "улучшений", такое дерево может выродиться в линейный список, где <tex>\mathrm{get}</tex> будет работать за линейное время, и никакого выигрыша по сравнению с [[СНМ(наивные_реализации)|наивными реализацимиреализациями]] не будет. Выигрыш в скорости можно получить, используя две эвристики: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).

Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен <tex>10</tex>. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на <tex>1</tex>.

Проведем анализ реализации с ранговой эвристикой. Будем доказывать, будем доказывать более слабую оценку (итерированный логарифм что амортизационная стоимость <tex>\mathrm{get} = \mathrm{O(\log^{*}n)} </tex>).

|definition='''Итерированный логарифм''' (англ. ''Iterated logarithm'') <tex>\mathrm({\log^*n)}</tex> — минимальное число логарифмирований <tex>n</tex>, необходимое для получения значения, не превосходящего <tex>1</tex> (Например: <tex>\mathrm(\log^*_2 16) = 3</tex>).

'''Пример''': <tex>\mathrm{\log^*_2 16} = 3</tex> Рассмотрим <tex> n </tex> операций <tex> \mathrm{union} </tex> и <tex> m </tex> операций <tex> \mathrm{get} </tex>. Далее будем Можем считать, что число операций <tex>m\geqslant nmathrm{union} </tex>равно числу элементов множества, так как количество операций <tex>\mathrm{union}</tex> не превосходит количество элементов множества <tex>n</tex>. Заметим, что <tex>m\geqslant n</tex>, так как при каждом вызове операции <tex>\mathrm{union}</tex> дважды вызывается операция <tex>\mathrm{get}</tex>.

Иначе, из принципа работы функции <tex> \mathrm{getunion} </tex> следует:

#Между <tex> \mathrm{v } </tex> и <tex> \mathrm{P(v)} </tex> существует путь вида: <tex> \mathrm{v } \rightarrow \mathrm{L(v)} \rightarrow \mathrm{L(L(v))} \rightarrow \dots \rightarrow \mathrm{P(v)} </tex>.

<tex> \mathrm{R(v)} \leqslant \log_2n </tex>.

Рассмотрим все вызовы функции <tex>\mathrm{get(u)}</tex>. В процессе выполнения каждой операции двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Если вершина <tex>u</tex> не корень и не сын корня, то во время рекурсивных вызовов функции <tex>\mathrm{get(u)}</tex> текущее значение <tex>\mathrm{R(PL(u))}</tex> возрастает.

#:1. <tex>u</tex> — корень. Таких вызовов <tex>\mathrm{get(u)}</tex> будет ровно <tex>m</tex>;.#:2. <tex>u</tex> — сын корня. Таких вызовов <tex>\mathrm{get(u)}</tex> будет не больше чем <tex>m</tex>. Оставшиеся вершины разделим на:#:3. Быстро растущие вызовы — такие что <tex>\mathrm{R(P(u))} \geqslant i^{\mathrm{R(u)}}</tex>, где <tex>i</tex> — число из диапазона <tex dpi="150">e ^{\frac{1}{e}} < i < 2</tex>. <tex dpi="150">(e ^{\frac{1}{e}}\approx </tex> <tex>1.44</tex><tex dpi="150">)</tex>;.#:4. Медленно растущие вызовы — <tex>\mathrm{R(P(u))} < i^{\mathrm{R(u)}}</tex>.

При каждом вложенном вызове функции <tex>\mathrm{get(u)}</tex> для вершин третьего типа ранг вершины по условию возрастает на до <tex>i^{\mathrm{R(u)}}</tex>. Ранг вершины может меняться в пределах от <tex>10</tex> до <tex>\log_2n</tex>. Значит количество рекурсивных вызовов равняется количеству возведений в степень <tex>\mathrm{R(n)}</tex> числа <tex>i</tex>,необходимых для достижения числа <tex>\log_2n</tex>. Или что то же самое, количеству логарифмирований по основанию <tex>i</tex> числа <tex>\log_2n</tex> для получения <tex>1</tex> и еще одному логарифмированию для получения <tex>0</tex>. Последняя операция Количество логарифмирований описывается функцией <tex dpi="130">\log^*_{i} \left (\log_2 n \right )</tex>. С учетом последнего логарифмирования формула примет вид <tex dpi="130">\log^*_{i}n</tex>.