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