17
правок
Изменения
Нет описания правки
Эта эвристика аналогична [[СНМ(списки_с_весовой_эвристикой)|весовой эвристике у связных списков]]. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.
Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен <tex>1</tex>. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на <tex>1</tex>.
===Сжатие пути===
Эта эвристика несколько модифицирует операцию ''<tex>\mathrm{get}</tex>''. Операция <tex>\mathrm{get}</tex> вызывается для элемента ''<tex>x''</tex>, проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и ''<tex>x''</tex>. Поэтому мы можем подвесить (изменить ссылки) эти вершины напрямую к корню дерева и, таким образом, уменьшить его высоту. При нерекурсивной реализации операция ''<tex>\mathrm{get}</tex>'' становится двухпроходной.
===Псевдокод===
* <tex>\mathrm{\alpha(m, n)}</tex> {{---}} функция, обратная к функции Аккермана (если <tex>m</tex> операций get и <tex>n</tex> элементов).
Докажем, что если глубина множества (т.е. его ранг) равна <tex>k</tex>, то в нем содержится как минимум <tex>2^k</tex> элементов. Из этого свойства следует, что глубина множества с <tex>n </tex> элементами есть <tex>\mathrm{O(\log n)}</tex>, а значит и время работы операции <tex>\mathrm{get}</tex> является логарифмическим.
Будем доказывать данное свойство по индукции. Для <tex>k = 0</tex>, очевидно, в множестве содержится <tex>1 </tex> вершина. Пусть для множеств ранга <tex>k - 1 </tex> свойство выполняется. Как следует из ранговой эвристики, множество ранга <tex>k </tex> может получиться только при подвешивании множества ранга <tex>k - 1 </tex> к множеству ранга <tex>k - 1</tex>. Но тогда из предположения индукции в новом множестве действительно будет <tex>2^k</tex> вершин, что и требовалось доказать.
===Функция Аккермана===
Докажем по индукции:
Для <tex>0 </tex> равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>\mathrm{K(v)} \geqslant \mathrm{K(v_1)} + \mathrm{K(v_2)} \geqslant 2^{i-1}+2^{i-1} \geqslant 2^i </tex>.
Итак <tex> S = \mathrm{O(1)} + \mathrm{O(\log^*x)} + \mathrm{O(1)} = \mathrm{O(\log^*x)} </tex>.
В силу того, что интервал <tex>(1.45; 2) </tex> не пустой, теорема доказана.
}}
