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

Система непересекающихся множеств. Реализация с помощью леса корневых деревьев. (disjoint set union (DSU) или Union-Find)

Реализация

Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель — один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".

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

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

Объединение по рангу

Эта эвристика аналогична весовой эвристике у связных списков. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.

Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен 1. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на 1.

Сжатие пути

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

Псевдокод

Для реализации СНМ будем поддерживать следующие массивы:

[math]p[x][/math] — массив "родителей".

[math]r[x][/math] — массив рангов.

get

get(x)
   if p[x] != x
      p[x] = get(p[x])
   return p[x]

union

union(x, y)
   x = get(x)
   y = get(y)
   if r[x] == r[y]
      r[x]++
   if r[x] < r[y]
      p[x] = y
   else
      p[y] = x

Асимптотика

см. также Анализ реализации с ранговой эвристикой

Операция	Истинное время	Амортизированное время
get	[math]O(\log n)[/math]	[math]O(\alpha(m, n))[/math]
union	[math]O(1)[/math]	[math]O(1)[/math]

• m — общее количество операций

• n — полное количество элементов

• [math]\alpha(m, n)[/math] — функция, обратная к функции Аккермана (если [math]m[/math] операций get и [math]n[/math] элементов).

Функция Аккермана

Функция Аккермана определяется следующим рекуррентным соотношением для целых неотрицательных чисел [math]m[/math] и [math]n[/math]:

[math]A(m, n) = \begin{cases} 2^n, & m = 1 \\ 2, & m \gt 1, n = 0 \\ A(m - 1, A(m, n - 1)), & m \gt 1, n \gt 0 \end{cases} [/math]

Таблица значений функции Аккермана:

[math]m \backslash n[/math]	0	1	2	3	4	5
1	1	2	4	8	16	32
2	2	4	16	65536	[math]2^{2^{16}}[/math]	[math]2^{2^{2^{16}}}[/math]
3	2	16	[math]\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}[/math]	[math]\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{A(3, 2)}[/math]	[math]\cdots[/math]	[math]\cdots[/math]
4	2	[math]\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}[/math]	[math]\cdots[/math]	[math]\cdots[/math]	[math]\cdots[/math]	[math]\cdots[/math]

Функция, обратная функции Аккермана — [math]\alpha(m, n)[/math]. Как видно из таблицы значений для функции Аккермана, обратная функции для всех мыслимых значений не превышает 4, то есть можно считать, что операция get выполняется за константное время.

Ссылки

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

Литература

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