223
правки
Изменения
м
В худшем случаеБез использования дополнительных "улучшений", такое дерево может выродиться в линейный список и get будет работать за линейное время, и тогда никакого выигрыша по сравнению с [[СНМ(наивные_реализации)|наивными реализацими]] не будет. Сильный выигрыш Выигрыш в скорости даст использование двух эвристикможно получить, используя дву эвристики: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).
Нет описания правки
При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''union''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''get'').
===Объединение по рангу===
===Сжатие пути===
Эта эвристика несколько модифицирует операцию ''get''. Операция get вызывается для элемента ''x'', проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и ''x''. Поэтому подвесим (изменим ссылки) их напрямую к корню дерева и, таким образом, уменьшим его высоту. При нерукурсивной нерекурсивной реализации операция ''get'' становится двухпроходной.
==Асимптотика==
