Структура данных с непересекающимся множеством

Непересекающееся множество/Объединение-найти лес
Тип	многопутевое дерево
Изобретенный	1964
Изобретён	Бернард А. Галлер и Майкл Дж. Фишер
Временная сложность в обозначении большого О Операция Средний Худший случай Поиск О (а( п )) (амортизировано) О (а( п )) (амортизировано) Вставлять О (1) О (1) Пространственная сложность Космос На ) ​ ​ На ) ​ ​

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

Хотя существует несколько способов реализации структур данных с непересекающимися множествами, на практике их часто отождествляют с конкретной реализацией, называемой лесом с непересекающимися множествами . Это специализированный тип леса , который выполняет объединения и находит почти постоянное амортизированное время . Для выполнения последовательности m операций сложения, объединения или поиска в лесу с непересекающимися множествами с n узлами требуется общее время O ( m α( n )) , где α( n ) — крайне медленно растущая обратная функция Аккермана . Непересекающиеся леса не гарантируют такую ​​производительность для каждой операции. Отдельные операции объединения и поиска могут занимать больше времени, чем постоянное время α( n ) , но каждая операция заставляет лес с непересекающимися множествами корректироваться так, чтобы последующие операции выполнялись быстрее. Непересекающиеся леса являются асимптотически оптимальными и практически эффективными.

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

История

Непересекающиеся леса были впервые описаны Бернардом А. Галлером и Майклом Дж. Фишером в 1964 году. В 1973 году их временная сложность была ограничена $O(\log ^{*}(n))$, повторный логарифм $n$, Хопкрофт и Ульман . В 1975 году Роберт Тарьян первым доказал $O(m\alpha (n))$ ( обратная функция Аккермана ) верхняя граница временной сложности алгоритма. Он также доказал, что это жестко. В 1979 году он показал, что это нижняя граница для определенного класса алгоритмов, включающих структуру Галлера-Фишера. В 1989 году Фредман и Сакс показали, что $\Omega (\alpha (n))$ (амортизированные) слова $O(\log n)$ биты должны быть доступны любой структуре данных с непересекающимися наборами для каждой операции, тем самым доказав оптимальность структуры данных в этой модели.

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

В 1994 году Ричард Дж. Андерсон и Хизер Уолл описали распараллеленную версию Union-Find, которую никогда не нужно блокировать.

В 2007 году Сильвен Коншон и Жан-Кристоф Филлиатр разработали полустойкую версию структуры данных леса с непересекающимся множеством и формализовали ее корректность с помощью помощника по доказательству Coq . «Полупостоянный» означает, что предыдущие версии структуры эффективно сохраняются, но доступ к предыдущим версиям структуры данных делает более поздние версии недействительными. Их самая быстрая реализация обеспечивает почти такую ​​же эффективность, как и непостоянный алгоритм. Они не выполняют анализ сложности.

Также были рассмотрены варианты структур данных с непересекающимися множествами, обеспечивающие лучшую производительность при решении ограниченного класса задач. Габоу и Тарьян показали, что если возможные объединения определенным образом ограничены, то возможен алгоритм с действительно линейным временем.

Представительство

Каждый узел в лесу с непересекающимися множествами состоит из указателя и некоторой вспомогательной информации: размера или ранга (но не того и другого). Указатели используются для создания родительских деревьев указателей , где каждый узел, не являющийся корнем дерева, указывает на своего родителя. Чтобы отличить корневые узлы от других, их родительские указатели имеют недопустимые значения, например циклическую ссылку на узел или контрольное значение. Каждое дерево представляет собой набор, хранящийся в лесу, причем члены набора являются узлами дерева. Корневые узлы предоставляют представителей множества: два узла находятся в одном наборе тогда и только тогда, когда корни деревьев, содержащих эти узлы, равны.

Узлы в лесу можно хранить любым удобным для приложения способом, но общепринятым методом является их хранение в массиве. В этом случае родители могут быть указаны по индексу их массива. Для каждой записи массива требуется Θ(log n ) бит памяти для родительского указателя. Для остальной части записи требуется сопоставимый или меньший объем памяти, поэтому количество битов, необходимых для хранения леса, равно Θ( n log n ) . Если реализация использует узлы фиксированного размера (тем самым ограничивая максимальный размер леса, который может быть сохранен), то необходимое хранилище является линейным по n .

Операции

Структуры данных с непересекающимися наборами поддерживают три операции: создание нового набора, содержащего новый элемент; Нахождение представителя множества, содержащего заданный элемент; и Объединение двух наборов.

Делаем новые наборы

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

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

function MakeSet(x) is
    if x is not already in the forest then
        x.parent := x
        x.size := 1     // if nodes store size
        x.rank := 0     // if nodes store rank
    end if
end function

Эта операция имеет постоянную временную сложность. В частности, инициализация Лес с непересекающимся множеством с n узлами требует O ( n ) время.

Отсутствие родительского узла, назначенного узлу, означает, что узел отсутствует в лесу.

На практике, MakeSet должна предшествовать операция, выделяющая память для хранения x . Поскольку выделение памяти является амортизированной операцией с постоянным временем, как и в случае с хорошей реализацией динамического массива , оно не меняет асимптотическую производительность леса случайного набора.

Нахождение представителей множества

The Find операция следует по цепочке родительских указателей от указанного узла запроса x до тех пор, пока не достигнет корневого элемента. Этот корневой элемент представляет набор, к которому принадлежит x , и может быть самим x . Find возвращает корневой элемент, которого он достиг.

Выполнение Find операция представляет собой важную возможность для улучшения леса. Время в Find операция тратится на поиск родительских указателей, поэтому более плоское дерево приводит к более быстрому Find операции. Когда Find выполняется, нет более быстрого способа добраться до корня, чем последовательное следование каждому родительскому указателю. Однако родительские указатели, посещенные во время этого поиска, могут быть обновлены, чтобы они указывали ближе к корню. Поскольку каждый элемент, посещаемый на пути к корню, является частью одного и того же набора, это не меняет наборы, хранящиеся в лесу. Но это делает будущее Find операции выполняются быстрее не только для узлов между узлом запроса и корнем, но и для их потомков. Это обновление является важной частью амортизированной гарантии производительности непересекающегося леса.

Существует несколько алгоритмов Find которые достигают асимптотически оптимальной временной сложности. Одно семейство алгоритмов, известное как сжатие пути , заставляет каждый узел между узлом запроса и корнем указывать на корень. Сжатие пути можно реализовать с помощью простой рекурсии следующим образом:

function Find(x) is
    if x.parent ≠ x then
        x.parent := Find(x.parent)
        return x.parent
    else
        return x
    end if
end function

Эта реализация делает два прохода: один вверх по дереву и один назад. Для хранения пути от узла запроса до корня требуется достаточно оперативной памяти (в приведенном выше псевдокоде путь неявно представлен с помощью стека вызовов). Это можно уменьшить до постоянного объема памяти, выполнив оба прохода в одном направлении. Реализация постоянной памяти дважды проходит от узла запроса к корню: один раз для поиска корня и один раз для обновления указателей:

function Find(x) is
    root := x
    while root.parent ≠ root do
        root := root.parent
    end while

    while x.parent ≠ root do
        parent := x.parent
        x.parent := root
        x := parent
    end while

    return root
end function

Тарьян и Ван Леувен также разработали однопроходной метод. Find алгоритмы, которые сохраняют ту же сложность в худшем случае, но более эффективны на практике. Это называется разделением пути и разделением пути пополам. Оба они обновляют родительские указатели узлов на пути между узлом запроса и корнем. При разделении пути каждый родительский указатель на этом пути заменяется указателем на прародителя узла:

function Find(x) is
    while x.parent ≠ x do
        (x, x.parent) := (x.parent, x.parent.parent)
    end while
    return x
end function

Уполовинивание пути работает аналогично, но заменяет только все остальные родительские указатели:

function Find(x) is
    while x.parent ≠ x do
        x.parent := x.parent.parent
        x := x.parent
    end while
    return x
end function

Объединение двух наборов

MakeSet создает 8 синглтонов.

После некоторых операций Union, некоторые наборы сгруппированы вместе.

Операция Union(x, y) заменяет набор, содержащий x , и набор, содержащий y , их объединением. Union первое использование Find определить корни деревьев, содержащих x и y . Если корни одинаковые, то больше делать нечего. В противном случае два дерева необходимо объединить. Это делается либо установкой родительского указателя корня x на y , либо установкой родительского указателя корня y на x .

Выбор того, какой узел станет родительским, влияет на сложность будущих операций с деревом. Если это сделать небрежно, деревья могут стать чрезмерно высокими. Например, предположим, что Union всегда делал дерево, содержащее x, поддеревом дерева, содержащего y . Начните с леса, который только что был инициализирован элементами. $1,2,3,\ldots ,n,$ и выполнить Union(1, 2), Union(2, 3), ..., Union(n - 1, n). Результирующий лес содержит одно дерево с корнем n , а путь от 1 до n проходит через каждый узел дерева. Для этого леса самое время бежать Find(1) О ​ ( п ) .

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

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

В случае объединения по размеру узел сохраняет свой размер, который представляет собой просто количество его потомков (включая сам узел). Когда деревья с корнями x и y объединяются, родительским становится узел с большим количеством потомков. Если два узла имеют одинаковое количество потомков, то любой из них может стать родительским. В обоих случаях размер нового родительского узла устанавливается равным новому общему количеству его потомков.

function Union(x, y) is
    // Replace nodes by roots
    x := Find(x)
    y := Find(y)

    if x = y then
        return  // x and y are already in the same set
    end if

    // If necessary, swap variables to ensure that
    // x has at least as many descendants as y
    if x.size < y.size then
        (x, y) := (y, x)
    end if

    // Make x the new root
    y.parent := x
    // Update the size of x
    x.size := x.size + y.size
end function

Количество бит, необходимое для хранения размера, очевидно, равно количеству бит, необходимому для хранения n . Это добавляет постоянный коэффициент к требуемому запасу леса.

Союз по рангу

При объединении по рангу узел сохраняет свой ранг , который является верхней границей его высоты. Когда узел инициализируется, его ранг устанавливается равным нулю. Чтобы объединить деревья с корнями x и y , сначала сравните их ранги. Если ранги разные, то родительским деревом становится большее дерево рангов, а ранги x и y не изменяются. Если ранги одинаковы, то любой из них может стать родителем, но ранг нового родителя увеличивается на единицу. Хотя ранг узла явно связан с его высотой, хранение рангов более эффективно, чем хранение высот. Высота узла может меняться во время Find операция, поэтому сохранение рангов позволяет избежать дополнительных усилий по поддержанию правильной высоты. В псевдокоде объединение по рангу выглядит так:

function Union(x, y) is
    // Replace nodes by roots
    x := Find(x)
    y := Find(y)

    if x = y then
        return  // x and y are already in the same set
    end if

    // If necessary, rename variables to ensure that
    // x has rank at least as large as that of y
    if x.rank < y.rank then
        (x, y) := (y, x)
    end if

    // Make x the new root
    y.parent := x
    // If necessary, increment the rank of x
    if x.rank = y.rank then
        x.rank := x.rank + 1
    end if
end function

Можно показать, что каждый узел имеет ранг $\lfloor \log n\rfloor$ или меньше. Следовательно, каждый ранг может храниться в O (log log n ) битах, а все ранги могут храниться в O ( n log log n ) битах. Это делает ряды асимптотически незначительной частью размера леса.

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

Временная сложность

Реализация леса с непересекающимся множеством, в которой Find не обновляет родительские указатели, и в котором Union не пытается контролировать высоту деревьев, может иметь деревья высотой O ( n ) . В такой ситуации Find и Union операции требуют времени O ( n ) .

Если реализация использует только сжатие пути, то последовательность n MakeSet операций, за которыми следует до n − 1 Union операции и f Find операций, имеет наихудшее время работы $\Theta (n+f\cdot \left(1+\log _{2+f/n}n\right))$.

Использование объединения по рангу, но без обновления родительских указателей во время Find, дает время работы $\Theta (m\log n)$ для m операций любого типа, до n из которых MakeSet операции.

Сочетание сжатия пути, разделения или деления пополам с объединением по размеру или рангу сокращает время выполнения m операций любого типа, до n из которых MakeSet операции, чтобы $\Theta (m\alpha (n))$. Это делает амортизированное время выполнения каждой операции $\Theta (\alpha (n))$. Это асимптотически оптимально, означающее, что каждая структура данных непересекающегося множества должна использовать $\Omega (\alpha (n))$ амортизированное время на одну операцию. Здесь функция $\alpha (n)$ – обратная функция Аккермана . Обратная функция Аккермана растет необычайно медленно, поэтому этот коэффициент равен 4 или меньше для любого n , которое действительно можно записать в физической вселенной. Это делает операции с непересекающимися множествами практически амортизированными за постоянное время.

Доказательство временной сложности Union-Find O(m log* n)

Точный анализ производительности непересекающегося леса довольно сложен. Однако существует гораздо более простой анализ, который доказывает, что амортизированное время для любого m Find или Union операций над лесом из несвязного множества, содержащим n объектов, равна O ( m log ^* n ) , где log ^* обозначает повторный логарифм .

Лемма 1. Поскольку функция поиска следует по пути к корню, ранг узла, с которым она сталкивается, увеличивается.

Доказательство

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

Лемма 2: Узел u , являющийся корнем поддерева ранга r, имеет как минимум $2^{r}$ узлы.

Доказательство

Первоначально, когда каждый узел является корнем собственного дерева, это тривиально верно. Предположим, что узел u ранга r имеет не менее 2 ^р узлы. Тогда, когда два дерева ранга r объединяются с помощью операции Union by Rank , получается дерево ранга r + 1 , корень которого имеет не менее $2^{r}+2^{r}=2^{r+1}$ узлы.

Лемма 3. Максимальное количество узлов ранга r не более ${\frac {n}{2^{r}}}.$

Доказательство

Из леммы 2 мы знаем, что узел u , являющийся корнем поддерева ранга r, имеет не менее $2^{r}$ узлы. мы получим Максимальное количество узлов ранга r , когда каждый узел ранга r является корнем дерева, имеющего ровно $2^{r}$ узлы. В этом случае количество узлов ранга r равно ${\frac {n}{2^{r}}}.$

Для удобства мы определяем здесь «ведро»: ведро — это набор, содержащий вершины с определенными рангами.

Мы создаем несколько сегментов и индуктивно помещаем в них вершины в соответствии с их рангами. То есть вершины с рангом 0 попадают в нулевую корзину, вершины с рангом 1 — в первую корзину, вершины с рангами 2 и 3 — во вторую корзину. Если B -е ведро содержит вершины с рангами из интервала $\left[r,2^{r}-1\right]=[r,R-1]$ тогда (B+1)-е ведро будет содержать вершины с рангами из интервала $\left[R,2^{R}-1\right].$

Доказательство $O(\log ^{*}n)$ Союз Найти

Мы можем сделать два замечания относительно ведер.

1. Общее количество сегментов не превышает log ^* н

   Доказательство: Когда мы переходим от одного ведра к другому, мы прибавляем к степени еще одну двойку, то есть следующее ведро к $\left[B,2^{B}-1\right]$ будет $\left[2^{B},2^{2^{B}}-1\right]$

2. Максимальное количество элементов в сегменте $\left[B,2^{B}-1\right]$ самое большее ${\frac {2n}{2^{B}}}$

   Доказательство: максимальное количество элементов в ведре. $\left[B,2^{B}-1\right]$ самое большее ${\frac {n}{2^{B}}}+{\frac {n}{2^{B+1}}}+{\frac {n}{2^{B+2}}}+\cdots +{\frac {n}{2^{2^{B}-1}}}\leq {\frac {2n}{2^{B}}}.$

Пусть F представляет собой список выполненных операций «поиска», и пусть

$$T_{1}=\sum _{F}{\text{(link to the root)}}$$ $$T_{2}=\sum _{F}{\text{(number of links traversed where the buckets are different)}}$$ $$T_{3}=\sum _{F}{\text{(number of links traversed where the buckets are the same).}}$$

Тогда общая стоимость m находок равна $T=T_{1}+T_{2}+T_{3}.$

Поскольку каждая операция поиска совершает ровно один обход, ведущий к корню, имеем T ₁ = O ( m ) .

Кроме того, исходя из приведенной выше оценки количества сегментов, мы имеем T ₂ = O ( m log ^* н ) .

для T3 _{Предположим, что} мы пересекаем ребро от u до v , где u и v имеют ранги в ведре [ B , 2 ^Б − 1] и v не является корнем (во время этого обхода, иначе обход был бы учтен в T ₁ ). Зафиксируем u и рассмотрим последовательность $v_{1},v_{2},\ldots ,v_{k}$ которые играют роль v в различных операциях поиска. Из-за сжатия пути и отсутствия учета ребра до корня эта последовательность содержит только разные узлы, и благодаря лемме 1 мы знаем, что ранги узлов в этой последовательности строго возрастают. Поскольку оба узла находятся в ведре, мы можем заключить, что длина k последовательности (количество раз, когда узел u присоединен к другому корню в одном и том же ведре) не превышает количества рангов в ведре B , что это, самое большее $2^{B}-1-B<2^{B}.$

Поэтому, $T_{3}\leq \sum _{[B,2^{B}-1]}\sum _{u}2^{B}.$

Из наблюдений 1 и 2 можно сделать вывод, что ${\textstyle T_{3}\leq \sum _{B}2^{B}{\frac {2n}{2^{B}}}\leq 2n\log ^{*}n.}$

Поэтому, $T=T_{1}+T_{2}+T_{3}=O(m\log ^{*}n).$

Другие структуры

Лучшее время на операцию в худшем случае

Самое худшее время Find операция в деревьях с объединением по рангу или объединением по весу $\Theta (\log n)$ (т.е. это $O(\log n)$ и эта граница точная). В 1985 году Н. Блюм дал реализацию операций, не использующую сжатия путей, но сжимающую деревья во время $union$. Его реализация выполняется в $O(\log n/\log \log n)$ время на операцию, и, таким образом, по сравнению со структурой Галлера и Фишера она имеет лучшее время на операцию в худшем случае, но худшее амортизированное время. В 1999 году Альструп и др. дал структуру, которая имеет оптимальный наихудший случай время $O(\log n/\log \log n)$ вместе с амортизированным временем обратного Аккермана.

Удаление

Обычная реализация в виде непересекающихся лесов плохо реагирует на удаление элементов. в том смысле, что пришло время Find не улучшится в результате уменьшения количества элементов. Однако существуют современные реализации, которые допускают удаление в постоянное время и где ограничение по времени для Find зависит от текущего количества элементов

Приложения

Демо-версия Union-Find при использовании алгоритма Крускала для поиска минимального связующего дерева.

Структуры данных с непересекающимися наборами моделируют разделение набора , например, для отслеживания связанных компонентов неориентированного графа . Затем эту модель можно использовать, чтобы определить, принадлежат ли две вершины одному и тому же компоненту или приведет ли добавление ребра между ними к циклу. Алгоритм Union-Find используется в высокопроизводительных реализациях унификации .

Эта структура данных используется библиотекой Boost Graph для реализации функций дополнительных связанных компонентов . Это также ключевой компонент в реализации алгоритма Краскала для поиска минимального остовного дерева графа.

Алгоритм Хошена-Копельмана использует в алгоритме поиск объединения.

См. также

• Уточнение разделов — другая структура данных для поддержки непересекающихся наборов с обновлениями, которые разделяют наборы на отдельные, а не объединяют их вместе.
• Динамическое подключение

Внешние ссылки

• Реализация C++ , часть библиотек Boost C++.
• Реализация Java , часть библиотеки JGraphT
• Реализация Javascript
• Реализация Python