Изменения

Реализация системы непересекающихся множеств с помощью [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|леса корневых деревьев]] не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за истинную <tex>O(1)</tex>, сохраняя асимптотику для операций <tex>\mathrm{ Union } </tex> и <tex>\mathrm{Find}</tex> и потребление памяти <tex>O(n)</tex>.

Наша структура данных должна поддерживать следующие операции:

Как и в [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|обычной реализации]], выполнено следующее: <tex>rank(v) < rank(p(v))</tex>

В реализации СНМ с помощью леса корневых деревьев мы не можем удалить произвольную вершину из множества за разумное время - в таком случае нам придется переподвешивать <tex>O(n) </tex> поддеревьев этой вершины. Однако, если вершина является листом, то ее можно удалять совершенно безболезненно. <br />

;Соображение 1 : Пусть мы умеем менять произвольные вершины местами за <tex>O(1)</tex>. Тогда для удаления некоторой вершины достаточно поменять ее местами с каким-нибудь листом и удалить этот лист. <br />

Все дальнейшие усилия направлены на то, чтобы поддержать эти 2 операции, не испортив при этом асимптотику всех остальных.

Расширим [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|лес корневых деревьев]] следующим образом:

* Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список <tex> \mathrm{C_{list}} </tex> ее детей. Будем считать, что дети упорядочены по направлению списка слева направо.

* Каждая вершина, среди детей которой есть хотя бы 1 нелистовая вершина, имеет не менее 3 детей (это не позволяет дереву вытягиваться в бамбук, например)

Тривиально:

# Создадим узел <tex>v</tex> и свяжем его с элементом <tex>x</tex>. Установим: <tex>p(v) := v, rank(v) := 0</tex>

Очевидно, что операция соблюдает инварианты и выполняется за <tex>O(1)</tex>

Пусть <tex> T_A, T_B </tex> {{---}} деревья, реализующие множества <tex>A</tex> и <tex>B</tex> соответственно.

Пусть размер одного из деревьев меньше 4; не умаляя общности {{---}} <tex>size(T_B) < 4</tex>. Тогда действуем следующим образом:

Без учета вызова процедуры <tex>\mathrm {Find}</tex> мы сделаем <tex>O(1)</tex> операций.

В нашей реализации операции <tex>\mathrm {Find}</tex> вместо уже известного нам метода '''сжатия путей (path compressing)''' мы будем использовать '''разделение путей (path splitting)'''. Он заключается в том, чтобы при выполнении операции <tex>\mathrm {Find}</tex> перевешивать элемент, от которого мы вызвались, не сразу к корню, а к собственному "дедушке". Такой метод сокращения пути приводит к той же амотризационной оценке для функции <tex>\mathrm {Find}</tex><ref>[http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Union-Find-Tarjan.pdf|Robert E. Tarjan and Jan van Leeuwen. Worst-case analysis of set union algorithms. Journal of the ACM, 31(2):245–281, 1984.]</ref>, несмотря на то, что интуитивно кажется более медленным. Мы будем использовать именно разделение путей, потому что это серьезно упрощает поддержку списков и инвариантов.<br/>

Реализуем процедуру <tex> \mathrm { Relink(x) } </tex> {{---}} переподвешивание элемента <tex>x</tex> к его "дедушке" с сохранением инвариантов и структуры списков.

Очевидно, что <tex>\mathrm{Relink} </tex> выполняется за <tex>O(1)</tex>

Реализуем собственно операцию <tex>\mathrm{Find(a)}</tex>:

# Пусть <tex>x</tex> {{---}} вершина дерева, ассоциированная с элементом <tex>a</tex>

## <tex>x := t</tex>

Сначала разработаем процедуру удаления узла из дерева, у которого <tex>size(T) \leq 4</tex> {{---}} удаление из такого дерева даст нам сокращенное дерево. Назовем эту процедуру <tex>\mathrm{ReducedTreeDelete(a)} </tex>.

# Если дерево не сокращенное, сделаем его сокращенным, просто переподвесив все вершины к корню. Так как дерево маленькое {{---}} <tex>size(T) \leq 4</tex> {{---}} операция выполняется за <tex>O(1)</tex>

# Если <tex>a</tex> ассоциирован с листом, просто удалим этот лист.

Теперь подумаем, как удалять элемент из полного дереве размера больше 4. После удаления дерево должно остаться полным. <br/>

Нам необходимо найти некоторый лист дерева, из которого мы удаляем элемент. Реализуем для этого процедуру <tex>\mathrm{FindLeaf(a)}</tex>.

# Пусть элемент <tex>a</tex> ассоциирован с вершиной <tex>x</tex>.

# Если <tex>x</tex> {{---}} лист, задача решена.

Итак, мы нашли некоторый лист дерева за <tex>O(1)</tex>. Теперь нам нужно просто уметь его удалять, но так, чтобы инварианты и структура списков сохранялись.

Пусть <tex>x</tex> {{---}} удаляемый лист.

# Извлекаем <tex>x</tex> из <tex>\mathrm{C_{LIST}} \; p(x) </tex> и из <tex>\mathrm{DFS_{LIST}}</tex>

<br/>

Итак, соберем воедино операцию <tex>\mathrm{Delete(a)}</tex>:

Пусть элемент <tex>a</tex> ассоциирован с вершиной <tex>x</tex>

# Если <tex>size(T) \leq 4</tex>, вызываем <tex>\mathrm{ReducedTreeDelete(a)}</tex>

## <tex>\mathrm{DeleteLeaf(l)}</tex>

<references />

* [http://www2.mta.ac.il/~amirben/downloadable/ufd.pdf A Simple And Efficient Union-Find-Delete Algorithm]