СНМ (реализация с помощью леса корневых деревьев)

Эта статья находится в разработке!

Реализация

В реализации системы непересекающихся множеств с помощью леса корневых деревьев каждое множество представляется в виде дерева, в узлах которого находятся элементы самого множества. Каждое множество идентифицируется по его представителю. Каждый узел дерева хранит в себе ссылку на родителя, а корень дерева ссылается сам на себя и является представителем этого множества. При объединении двух множеств, один из корней деревьев подвешивается к другому (операция union). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по дереву вверх до корня (операция get).

Сама по себе такая реализация еще не дает выигрыша в скорости, по сравнению с наивными реализациями, так как при неудачном стечении обстоятельств дерево может выродиться в линейный список и get будет работать за линейное время. Выигрыш в скорости даёт использование двух эвристик: объединение по рангу (union by rank) и сжатие пути (path compression).

Асимптотика

Реализация системы непересекающихся множеств с помощью леса корневых деревьев дает следующие асимптотически оценки для операций:

get	a(m,n)
union	1
m*get + n*union	m*a(m,n) + n

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

Ссылки

• Система непересекающихся множеств - описание этой реализации на habrahabr.ru
• Функция Аккермана - Википедия

Литература

• Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Вильямс, 2010. - 1296с. — ISBN 978-5-8459-0857-4, 0-07-013151-1. (стр 589)