СНМ (реализация с помощью леса корневых деревьев)
Содержание
Реализация
В реализации системы непересекающихся множеств с помощью леса корневых деревьев каждое множество представляется в виде дерева, в узлах которого находятся элементы самого множества. Каждое множество идентифицируется по его представителю. Каждый узел дерева хранит в себе ссылку на родителя, а корень дерева ссылается сам на себя и является представителем этого множества. При объединении двух множеств, один из корней деревьев подвешивается к другому (операция 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)
