Лес непересекающихся множеств
Лес непересекающихся множеств — древовидная структура данных для непересекающихся множеств. (иногда называют Системой непересекающихся множеств)
Представление множеств
Каждое множество представляется в виде корневого дерева. В лесу непересекающихся множеств каждый узел содержит один элемент множества и указывает только на свой родительский узел. Корень каждого дерева содержит представителя и является родительским для самого себя.
Операции над лесом непересекающихся множеств выполняются следующим образом:
MAKE_SET — создает дерево с одним узлом.
FIND_SET — передвигаемся по родительским ссылкам до корня дерева.
UNION — устанавливает указатель корня одного дерева на корень другого.
Эвристики для повышения эффективности
Объединение по рангу. Идея эвристики состоит в том, чтобы при выполнении операции UNION высота итогового дерева по возможности не увеличивалась. Для этого используется характеристика ранг для каждого корня, которая представляет собой верхнюю границу высоты узла. Операция MAKE_SET создаёт корень с рангом 0. Операция UNION, которая в этом случае называется объединение по рангу, действует следующим образом:
- Если ранги корней различны, корень с меньшим рангом указывает на корень с большим рангом. Ранги корней не меняются.
- Если ранги корней равны, любой из корней указывает на другой. Ранг того корня, на который указывает другой корень, увеличивается на 1.
Сжатие путей. Эвристика в процессе выполнения операции FIND_SET делает каждый узел (которые встретились при передвижении до корня) указывающим непосредственно на корень. Сжатие путей не изменяет ранги узлов.
Псевдокод
Рассмотрим пример реализации леса непересекающихся множеств. В массиве p будем хранить ссылку на родительских узел, а в массиве r ранг вершины.
operation MAKE_SET(x) p[x] = x r[x] = 0
operation FIND_SET(x) if x ≠ p[x] then p[x] = FIND_SET(p[x]) return p[x]
operation UNION(x, y) if r[x] > r[y] then p[y] = x else p[x] = y if r[x] = r[y] then r[y] = r[y] + 1
Время работы
Будучи примененным раздельно, объединение по рангу и сжатие путей приводят к повышению эффективности операций над лесом непересекающихся множеств. Объединение по рангу само по себе дает время работы [math]\displaystyle{ O(m~\lg{n}) }[/math], где [math]\displaystyle{ m }[/math] — общее количество операций, а [math]\displaystyle{ n }[/math] — количество элементов в системе. Сжатие путей само по себе приводит ко времени работы в наихудшем случае [math]\displaystyle{ O(n + f~\log_{2 + f/n}{n}) }[/math], где [math]\displaystyle{ f }[/math] — количество операций FIND_SET. Применение обеих эвристик дает время работы в наихудшем случае [math]\displaystyle{ O(m\ \alpha(n, m)) }[/math], где [math]\displaystyle{ \alpha(n, m) }[/math] — обратная функция Аккермана. Эта оценка является нижней границей времени работы с непересекающимися множествами, поэтому лес непересекающихся множеств является оптимальной структурой для непересекающихся множеств.