Изменения

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

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

где m - общее количество операций, n - полное количество элементов, a(m, n) - функция, обратная функция к функции Аккермана - очень медленно растущая функция и практически для всех разумных значений не превышает 4, поэтому ее можно считать константой.   Таким образом, при этой реализации время работы линейно зависит от количества операций.