Изменения

Реализация системы непересекающихся множеств с помощью [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|леса корневых деревьев]] не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за истинную <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>

Докажем верхнюю оценку стоимости операции <tex>\mathrm{Find}</tex> в <tex>O(\log {n})</tex>.

{{Определение

Докажем теперь, что каждая из операций сохраняет инвариант 3.

Т. к. операция <tex>\mathrm{Makeset}</tex> создает сокращенное дерево, то по лемме 1 <tex>\mathrm{Makeset}</tex> сохраняет инвариант 3

Пусть для множеств <tex>A</tex> и <tex>B</tex> инвариант 3 выполняется. <br/>

Пусть <tex>C = \mathrm{Union(A, B)}</tex>. Пусть, не умаляя общности, <tex>rank(A) > rank(B)</tex>. Тогда мы подвесим <tex>T_B</tex> к корню <tex>T_A</tex>, и <tex>rank(C)</tex> будет равным <tex>rank(A)</tex>, и следовательно, <br/><br/><center><tex>VAL(C) > VAL(A) \geq 2^{rank(A)} = 2^{rank(C)}</tex></center><br/>

Следовательно, операция <tex>\mathrm{Union}</tex> сохраняет инвариант 3.

Пусть для множества <tex>A</tex> инвариант 3 выполняется. <br>

Операция <tex>\mathrm{Find}</tex> изменяет дерево <tex>T_A</tex>. Если после выполнения <tex>\mathrm{Find} \; T_A</tex> стало сокращенным, то инвариант 3 сохранен по лемме 1. <br/>

<br/> Так как <tex>\mathrm{Find}</tex> изменяет <tex>T_A</tex> только посредством операции <tex>\mathrm{Relink}</tex>, достаточно доказать, что <tex>\mathrm{Relink}</tex> сохраняет инвариант 3.

Операция <tex>\mathrm{Relink}</tex> переподвешивает узел <tex>x</tex> к <tex>p(p(x))</tex>. <br/> Пусть <tex>y = p(x), g = p(y), k = rank(g) \Rightarrow rank(y) \leq k - 1</tex>. Следовательно, до переподвешивания <tex>val(x) = \left( \frac{3}{2} \right)^{k - 1}</tex>, а после переподвешивания <tex>val(x) \leq \left( \frac{3}{2} \right)^{k}</tex>. Таким образом, при переподвешивании <tex>x \; VAL(A)</tex> может только увеличиться. Тем временем <tex>rank(A)</tex> остается неизменным, ведь <tex>\mathrm{Relink}</tex> меняет ранг корня только тогда, когда дерево стало сокращенным, а сейчас мы рассматриваем только полные деревья. Из этого вытекает: <br><center><tex>VAL(A') \geq VAL(A) \geq 2^{rank(A)} = 2^{rank(A')}</tex></center><br>

Итак, операция <tex>\mathrm{Relink}</tex> сохраняет инвариант 3, следовательно {{---}} операция <tex>\mathrm{Find}</tex> сохраняет инвариант 3.

Пусть для множества <tex>A</tex> инвариант 3 выполняется. <br>

Если после выполнения <tex>\mathrm{Delete} \; T_A</tex> стало сокращенным, то инвариант 3 сохранен по лемме 1. <br/>

Так как операция <tex>\mathrm{FindLeaf}</tex> и обмен элементами между узлами не меняют структуры дерева, достаточно рассмотреть операцию <tex>\mathrm{DeleteLeaf}</tex>.

Пусть <tex>x</tex> {{---}} удаляемый элемент, <tex>y = p(x)</tex>.

* Если <tex>y \neq root</tex>, то обозначим <tex>g = p(y), k = rank(g) \Rightarrow rank(y) \leq k - 1</tex>. Мы удаляем <tex>x</tex> и отсоединяем 2 его братьев, их суммарное значение не больше <tex>3 \left( \frac {3} {2} \right) ^ {k - 1} </tex>. Потом мы подвешиваем 2 братьев к <tex>g</tex> {{---}} их суммарное значение становится <tex>2 \left( \frac {3} {2} \right) ^ k </tex>. Итого, суммарное изменение значения не меньше <br><center><tex>-3 \left( \frac {3} {2} \right) ^ {k - 1} + 2 \left( \frac {3} {2} \right) ^ k = 0</tex>,</center><br>

Итак, операция <tex>\mathrm{DeleteLeaf}</tex> сохраняет инвариант 3, а значит, и операция <tex>\mathrm{Delete} </tex> сохраняет его.

{{Лемма

|id=lemma_2

: <tex>\mathrm{Find}</tex> занимает <tex>O(\alpha (n))</tex> в среднем<ref>[https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/Union-Find%20with%20Constant%20Time%20Deletions.pdf|S. Alstrup, I. L. Gørtz, T. Rauhe, M. Thorup, and U. Zwick. Union-find with constant time deletions.]</ref>.

<references />

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

* [https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/Union-Find%20with%20Constant%20Time%20Deletions.pdf S. Alstrup, I. L. Gørtz, T. Rauhe, M. Thorup, and U. Zwick. Union-find with constant time deletions]