Лес непересекающихся множеств

Лес непересекающихся множеств — древовидная структура данных для непересекающихся множеств. (иногда называют Системой непересекающихся множеств)

Представление множеств

Каждое множество представляется в виде корневого дерева. В лесу непересекающихся множеств каждый узел содержит один элемент множества и указывает только на свой родительский узел. Корень каждого дерева содержит представителя и является родительским для самого себя.

Операции над лесом непересекающихся множеств выполняются следующим образом:

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] — обратная функция Аккермана. Эта оценка является нижней границей времени работы с непересекающимися множествами, поэтому лес непересекающихся множеств является оптимальной структурой для непересекающихся множеств.

Ссылки

• Визуализатор работы структуры данных

Литература

• {{#if:Томас Кормен и др.|Томас Кормен и др. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Алгоритмы: построение и анализ]]|{{#if:|[ Алгоритмы: построение и анализ]|Алгоритмы: построение и анализ}}}}{{#if:INTRODUCTION TO ALGORITHMS| = INTRODUCTION TO ALGORITHMS }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Алгоритмы: построение и анализ|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:2-е изд| — 2-е изд.}}{{#switch:{{#if:М.|м}}{{#if:«Вильямс»|и}}{{#if:2006|г}}

 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: «Вильямс», 2006.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: «Вильямс».
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}, 2006.
 |иг= — «Вильямс», 2006.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М..}} }}
 |и= — «Вильямс».
 |г= — 2006.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:1296| — С. 1296.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:0-07-013151-1| — ISBN 0-07-013151-1}}