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

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!

Система непересекающихся множеств. Реализация с помощью леса корневых деревьев. (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, поэтому ее можно считать константой. Таким образом, при этой реализации время работы линейно зависит от количества операций.

Ссылки

Литература

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