Изменения

== Введение Описание ==

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

* <tex>\mathrm {Makeset(x)}</tex> {{---}} создать новое множество из <tex>1</tex> элемента <tex>x </tex>. Время: <tex>O(1)</tex>.

* <tex>\mathrm {Find(x)}</tex> {{---}} найти множество, в котором содержится элемент <tex> x </tex>. Время: <tex>O(\log {n})</tex> в худшем случае, <tex>O(\alpha(n))</tex> {{---}} в среднем (<tex>\alpha(n)</tex> {{---}} обратная функция Аккермана), где <tex> n </tex> {{---}} размер множества.* <tex>\mathrm{Delete(x)}</tex> {{---}} удалить элемент x из содержащего его множества. Время: <tex>O(1)</tex>.

В дальнейшем мы будем использовать используются следующие понятия и обозначения:

* <tex>size(A)</tex> {{---}} размер множества <tex>A </tex> (количество элементов в нем).* <tex>root(T_A)</tex> {{---}} корень дерева <tex>T_A</tex>.* <tex>h(v)</tex> {{---}} высота вершины <tex>v</tex>: если <tex>v</tex> является листом, то <tex>h(v) = 0</tex>, иначе <tex>h(v) = \max \{ h(w) \: | \: w - \mathrm{ child \: of } \: v \} + 1</tex>.* <tex>p(v)</tex> {{---}} родитель вершины <tex>v</tex>. Если <tex>v</tex> {{---}} корень, то считаем, что <tex>p(v) = v</tex>.

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

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

Это нововведение, очевидно, позволит нам менять элементы в дереве местами за <tex>O(1)</tex>. 

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

Эти три нововведения необходимы для нахождения листа в дереве (как оказывается, это гораздо более нетривиальная задача).

|definition=Дерево, либо состоящее ровно из одной вершины, либо же из <tex>1</tex> вершины ранга <tex>1</tex> и листьев ранга <tex>0</tex>, называется '''сокращенным''' (англ. ''reduced'') .

# Создадим узел <tex>v</tex> и свяжем его с элементом <tex>x</tex>. Установим: <tex>p(v) := v, rank(v) := 0</tex>.# Создадим для вершины <tex>v</tex> пустые списки <tex>\mathrm{NL_N_{LIST}}</tex> и <tex>\mathrm{C_{LIST}}</tex>.# Создадим <tex>\mathrm{DFS_{LIST}}</tex> с одним элементом {{---}} вершина <tex>v</tex>.Очевидно, что операция соблюдает инварианты и выполняется за <tex>O(1)</tex>.

# <tex>\forall v \in T_B : \: p(v) := root(T_A), \: rank(v) := 0</tex>.# <tex> rank(root(T_A)) := \max \: \{ rank(root(T_A)), 1 \: \}</tex>.# Присоединим <tex>\mathrm{ DFS_{LIST}} </tex> и <tex>\mathrm{C_{LIST}}</tex> для <tex>T_B </tex> в конец <tex>\mathrm{ DFS_{LIST}} </tex> и <tex>\mathrm{C_{LIST}}</tex> для <tex>T_A</tex>.

# <tex>p(root(T_B)) := root(T_A)</tex>, и если <tex>rank(root(T_A)) = rank(root(T_B))</tex>, увеличим <tex>rank(root(T_A))</tex> на <tex>1</tex>.# Вставим <tex>root(T_B)</tex> в начала начало <tex>\mathrm{ N_{LIST}} </tex> и <tex>\mathrm{C_{LIST}}</tex> для <tex>T_A</tex>.# Вставим <tex>\mathrm{ DFS_{LIST}} </tex> для <tex>T_B </tex> в <tex>\mathrm{ DFS_{LIST}} </tex> для <tex>T_A </tex> сразу после <tex>root(T_A)</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> p(x) </tex> стал листом, присвоим <tex> rank(p(x)) := 0 </tex> и удалим <tex> p(x) </tex> из <tex>\mathrm{NL_N_{LIST}}</tex> корня дерева.# Если после этого <tex>\mathrm{NL_N_{LIST}}</tex> корня стал пустым (это значит, что дерево стало сокращенным), присвоим <tex> rank(root) := 1 </tex>

## <tex>t := p(x)</tex>

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

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

# Иначе найдем среди детей <tex>p(x)</tex> узел, не являющийся листом (с помощью <tex>\mathrm{NL_N_{LIST}}</tex>), и вызовем <tex>\mathrm{Relink}</tex> для <tex>3</tex> его самых правых детей.

## <tex>l := \mathrm{FindLeaf(a)} </tex>

|definition=Определим '''значение''' вершины <tex>v</tex> {{---}} <tex>val(v)</tex> {{---}} следующим образом: <br/><br/>   <texdpi='160'>val(v) = \left(\frac{3}{2} \right)^{rank(p(v))} </tex>

|definition='''Значение множества''' <tex>A</tex> {{---}} <tex>VAL(A)</tex> {{---}} сумма значений вершин <tex>T_A</tex>: <br/><br/>   <tex>VAL(A) = \sum\limits_{v \in T_A} {val(v)} </tex>

Так как в <tex>T_A</tex> есть <tex>|A|</tex> вершин и <texdpi='140'>val(v) \leqslant \left(\frac{3}{2} \right)^{rank(A)}</tex>, то: <br/> 

<texdpi='160'>

Если <tex>h(T_A) = 0</tex> (т. е. дерево состоит только из корня), то <texdpi='140'>VAL(A) = \left( \frac{3}{2} \right)^{0} = 1 </tex> и <tex> 2^{rank(A)} = 2^0 = 1 \Rightarrow VAL(A) = 2^{rank(A)} </tex>. <br/> Если <tex>h(T_A) = 1</tex>, то <texdpi='140'>VAL(A) \geqslant \left( \frac{3}{2} \right)^{1} + \left( \frac{3}{2} \right)^{0} = \frac{5}{2} </tex> и <tex>2^{rank(A)} = 2^1 = 2 \Rightarrow VAL(A) \geqslant 2^{rank(A)}</tex>

Пусть для множеств <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) \geqslant 2^{rank(A)} = 2^{rank(C)}</tex></center><br/> 

<br/><center><tex>VAL(C) > VAL(A) + VAL(B) \geqslant 2^{rank(A)} + 2^{rank(B)} = 2^{1 + rank(A)} = 2^{rank(C)} </tex></center><br/> 

Пусть для множества <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) \leqslant k - 1</tex>. Следовательно, до переподвешивания <tex>val(x) = \left( \frac{3}{2} \right)^{k - 1}</tex>, а после переподвешивания <tex>val(x) \leqslant \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') \geqslant VAL(A) \geqslant 2^{rank(A)} = 2^{rank(A')}</tex></center><br> 

Пусть для множества <tex>A</tex> '''инвариант 3 ''' выполняется. <br> Если после выполнения <tex>\mathrm{Delete} \; T_A</tex> стало сокращенным, то '''инвариант 3''' сохранен по '''лемме 1'''. <br/> Осталось рассмотреть случай, когда до и после выполнения <tex>\mathrm{Delete} \; T_A</tex> было полным. Обозначим множество <tex>A</tex> после выполнения <tex>\mathrm{Delete}</tex> как <tex>A'</tex><br/> 

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

<center><tex>VAL(A') \geqslant VAL(A)</tex></center><br> 

<br><center><tex>VAL(A') \geqslant VAL(A) \geqslant 2^{rank(A)} = 2^{rank(A')}</tex></center><br> 

* Если Если <tex>y = root</tex>, то обозначим <tex>k = rank(y) \Rightarrow rank(x) \leqslant k - 1</tex>. Обозначим некоторого брата <tex>x</tex>, не являющегося листом, как <tex>c \Rightarrow rank(c) \leqslant k - 1</tex>. Мы удаляем <tex>x</tex> и переподвешиваем <tex>3</tex> сыновей <tex>c</tex>, следовательно суммарное значение дерева сначала убывает на не более чем <texdpi='140'>\left( \frac {3} {2} \right) ^ k + 3 \left( \frac {3} {2} \right) ^ {k - 1}</tex> а после увеличивается на <texdpi='140'>3 \left( \frac {3} {2} \right) ^ k </tex>. Итого, суммарное изменение значения не меньше чем<center><texdpi='140'> -\left( \frac {3} {2} \right) ^ k - 3 \left( \frac {3} {2} \right) ^ {k - 1} + 3 \left( \frac {3} {2} \right) ^ k</tex>,</center>

<center><tex>VAL(A') \geqslant VAL(A) \geqslant 2^{rank(A)} = 2^{rank(A')}</tex></center><br> 

: <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>.

== Ссылки Источники информации ==

* [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Система непересекающихся множеств ]]