СНМ (реализация с помощью леса корневых деревьев)
Система непересекающихся множеств. Реализация с помощью леса корневых деревьев. (disjoint set union (DSU) или Union-Find)
Содержание
Реализация
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель - один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме элемента множества, хранится ссылка на "родителя".
При объединении двух множеств, корень одного дерева подвешивается к другому (операция union). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция get).
Сама по себе такая реализация еще не дает выигрыша в скорости, в сравнении с наивными реализациями, так как при неудачном стечении обстоятельств дерево может выродиться в линейный список и get будет работать за линейное время. Сильный выигрыш в скорости даст использование двух эвристик: объединение по рангу (union by rank) и сжатие пути (path compression).
Объединение по рангу
Эта эвристика аналогична |весовой эвристике у связных списков. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.
Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней границей высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен 1. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое, к какому подвешивать, но ранг объединенного дерева будет больше на 1.
Сжатие пути
Эта эвристика несколько модифицирует операцию get и делает ее двухпроходной. Операция get вызывается для элемента x (get(x)), проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и x. Поэтому подвесим их напрямую (изменим ссылки) к корню дерева и, таким образом уменьшим его высоту.
Асимптотика
Реализация системы непересекающихся множеств с помощью леса корневых деревьев дает следующие асимптотически оценки для операций:
| 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)
