СНМ (реализация с помощью леса корневых деревьев)
Содержание
Реализация
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель — один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".
При объединении двух множеств, корень одного дерева подвешивается к другому (операция union). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция get).
Без использования дополнительных "улучшений", такое дерево может выродиться в линейный список, где get будет работать за линейное время, и никакого выигрыша по сравнению с наивными реализацими не будет. Выигрыш в скорости можно получить, используя две эвристики: объединение по рангу (union by rank) и сжатие пути (path compression).
Объединение по рангу
Эта эвристика аналогична весовой эвристике у связных списков. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.
Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен 1. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на 1.
Сжатие пути
Эта эвристика несколько модифицирует операцию get. Операция get вызывается для элемента x, проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и x. Поэтому мы можем подвесить (изменить ссылки) эти вершины напрямую к корню дерева и, таким образом, уменьшить его высоту. При нерекурсивной реализации операция get становится двухпроходной.
Псевдокод
Для реализации СНМ будем поддерживать следующие массивы:
— массив "родителей".
— массив рангов.
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 x == y
return;
if r[x] == r[y]
r[x]++
if r[x] < r[y]
p[x] = y
else
p[y] = x
Асимптотика
- см. также Анализ реализации с ранговой эвристикой
| Операция | Истинное время | Амортизированное время |
|---|---|---|
| get | ||
| union |
- m — общее количество операций
- n — полное количество элементов
- — функция, обратная к функции Аккермана (если операций get и элементов).
Докажем, что если глубина множества (т.е. его ранг) равна k, то в нем содержится как минимум элементов. Из этого свойства следует, что глубина множества с n элементами есть , а значит и время работы операции get является логарифмическим.
Будем доказывать данное свойство по индукции. Для k = 0 очевидно в множестве содержится 1 вершина. Пусть для множеств ранга k - 1 свойство выполняется. Как следует из ранговой эвристики, множество ранга k может получиться только при подвешивании множества ранга k - 1 к множеству ранга k - 1. Но тогда из предположения индукции в новом множестве действительно будет вершин, что и требовалось доказать.
Функция Аккермана
Функция Аккермана определяется следующим рекуррентным соотношением для целых неотрицательных чисел и :
Таблица значений функции Аккермана:
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 4 | 8 | 16 | 32 |
| 2 | 2 | 4 | 16 | 65536 | ||
| 3 | 2 | 16 | ||||
| 4 | 2 |
Функция, обратная функции Аккермана равна минимальному такому, что . Как видно из таблицы значений для функции Аккермана, обратная функции для всех мыслимых значений не превышает 4, то есть можно считать, что операция get выполняется за константное время.
Ссылки
- Система непересекающихся множеств — описание этой реализации на habrahabr.ru
- Функция Аккермана — Википедия
Литература
- Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Вильямс, 2010. - 1296с. — ISBN 978-5-8459-0857-4, 0-07-013151-1. (стр 589)
