Изменения

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

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

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

* <tex>makeset\mathrm {Makeset(x)}</tex> {{- --}} создать новое множество из <tex>1 </tex> элемента <tex>x </tex>. Время: <tex>O(1)</tex>.* <tex>union\mathrm {Union(A, B)}</tex> {{- --}} объединить множества <tex>A </tex> и <tex>B </tex> в одно. Время: <tex> O(1) </tex>, без учета времени на операцию <tex>find()\mathrm{Find}</tex>, которая используется, если множества <tex>A </tex> и <tex>B </tex> заданы своими произвольными представителями.* <tex>find\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>delete\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)</tex> {{-- -}} ранг вершины, некоторая верхняя оценка на ее высоту.  Как и в [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|обычной реализациис помощью леса корневых деревьев]], выполнено следующее: <tex>rank(v) < rank(p(v))</tex>. == Идея ==В реализации СНМ с помощью леса корневых деревьев нет возможности удалить произвольную вершину из множества за разумное время {{---}} в таком случае придется переподвешивать <tex>O(n) </tex> поддеревьев этой вершины. Однако, если вершина является листом, то ее можно удалять совершенно безболезненно. ;Соображение 1 : Пусть есть возможность менять произвольные вершины местами за <tex>O(1)</tex>. Тогда для удаления некоторой вершины достаточно поменять ее местами с каким-нибудь листом и удалить этот лист. ;Соображение 2 : Пусть есть возможность находить какой-нибудь лист (неважно, какой именно) в дереве за <tex>O(1)</tex>. Тогда, по '''соображению 1''ранг родителя вершин ', мы уже умеем удалять произвольный элемент из дерева за <tex>O(1)</tex>. Все дальнейшие усилия направлены на то, чтобы поддержать эти <tex>2</tex> операции, не испортив при этом асимптотику всех остальных.

==== Модификации для 1-го соображения ====Разделим понятия '''вершина дерева''' и '''элемент множества''': * '''вершиной дерева''' назовем объект, содержащий ссылки <tex>next</tex>, <tex>prev</tex> и <tex>head</tex> (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине '''элемент множества''';* '''элемент множества''' {{---}} объект, содержащий значение элемента и ссылку на соотв. '''вершину дерева'''.Это нововведение, очевидно, позволит менять элементы в дереве местами за <tex>O(1)</tex>. ==== Модификации для 2-го соображения ====* Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список <tex> \mathrm{C_{listLIST}} </tex> ее детей. Будем считать, что дети упорядочены по направлению списка слева направо.* Для корня каждого дерева храним двусвязный список <tex> \mathrm{NL_N_{listLIST}} </tex> его детей, не являющихся листьями.* Для каждого дерева (включая поддеревья) храним циклический двусвязный список <tex> \mathrm{DFS_{listLIST}} </tex> его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.* Разделим понятия '''вершина дерева''' и '''элемент множества''': ** '''вершиной дерева''' назовем объектЭти три нововведения необходимы для нахождения листа в дереве (как оказывается, содержащий ссылки <tex>next</tex>, <tex>prev</tex> и <tex>head</tex> (где необходимоэто гораздо более нетривиальная задача) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине '''элемент множества''';** '''элемент множества''' - объект, содержащий значение элемента и ссылку на соотв. '''вершину дерева'''.

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

|definition=Дерево называется '''полным'''(англ. ''full''), если каждый из его узлов либо является листом с рангом <tex>0</tex>, либо имеет не менее <tex>3 </tex> детей.

В нашей структуре данных будет поддерживаться следующий инвариант: '''дерево является либо только полным, либо только сокращеннымвсегда полное или сокращенное'''.

* Все деревья (и поддеревья) размера <tex>< 4 </tex> {{-- -}} сокращенные, а <tex>= \geqslant 4 </tex> {{--- }} полные* Каждая вершина, среди детей которой есть хотя бы <tex>1 </tex> нелистовая вершина, имеет не менее <tex>3 </tex> детей (это не позволяет дереву вытягиваться в бамбук, например) === Реализация операции Makeset ===Тривиально:# Создадим узел <tex>v</tex> и свяжем его с элементом <tex>x</tex>. Установим: <tex>p(v) = v, rank(v) = 0</tex>.# Создадим для вершины <tex>v</tex> пустые списки <tex>\mathrm{N_{LIST}}</tex> и <tex>\mathrm{C_{LIST}}</tex>.# Создадим <tex>\mathrm{DFS_{LIST}}</tex> с одним элементом {{---}} вершина <tex>v</tex>.Очевидно, что операция соблюдает инварианты и выполняется за <tex>O(1)</tex>. === Реализация операции Union ===Пусть <tex> T_A, T_B </tex> {{---}} деревья, реализующие множества <tex>A</tex> и <tex>B</tex> соответственно.Пусть размер одного из деревьев меньше <tex>4</tex>; не умаляя общности {{---}} <tex>size(T_B) < 4</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>4</tex>.Примем, не умаляя общности, что <tex>rank(root(T_A)) \geqslant rank(root(T_B))</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{ N_{LIST}} </tex> для <tex>T_B </tex> пустым. (Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную) Если в качестве идентификаторов множеств нам переданы произвольные представители этих множеств, нам придется запустить процедуру <tex>\mathrm {Find}</tex> для каждого из них, чтобы найти корни деревьев. Без учета вызова процедуры <tex>\mathrm {Find}</tex> мы сделаем <tex>O(1)</tex> операций. === Реализация операции Find ===В нашей реализации операции <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>, несмотря на то, что интуитивно кажется более медленным. Мы будем использовать именно разделение путей, потому что это серьезно упрощает поддержку списков и инвариантов.==== Операция Relink ====Реализуем процедуру <tex> \mathrm { Relink(x) } </tex> {{---}} переподвешивание элемента <tex>x</tex> к его "дедушке" с сохранением инвариантов и структуры списков.  # Удалим <tex> x </tex> из <tex> \mathrm{C_{LIST}} \; p(x)</tex> и вставим его в <tex> \mathrm{C_{LIST}} \; p(p(x))</tex> следующим образом:#* Если <tex>x</tex> имеет брата справа от себя, вставим его в <tex> \mathrm{C_{LIST}} \; p(p(x))</tex> сразу слева от <tex> p(x) </tex>#* Иначе (если <tex> x </tex> {{---}} крайний правый сын <tex>p(x)</tex>) {{---}} вставим <tex> x </tex> сразу справа от <tex> p(x) </tex># Обновим <tex> \mathrm {DFS_{LIST}} </tex> следующим образом:#* Если <tex>x</tex> {{---}} крайний правый сын <tex>p(x)</tex>, то на предыдущем шаге мы вставили его в список детей <tex>p(p(x))</tex> сразу после <tex>p(x)</tex>, следовательно {{---}} порядок обхода вершин из <tex> p(p(x)) </tex> в глубину не изменился. Значит, нам не нужно менять <tex> \mathrm {DFS_{LIST}} </tex>.#* В противном случае нам нужно поместить участок <tex> \mathrm {DFS_{LIST}} </tex>, соответствующий поддереву <tex>x</tex>, перед <tex>p(x) </tex>. Этот участок {{---}} полуинтервал <tex>[x, l)</tex>, где <tex>l</tex> {{---}} сосед <tex>x</tex> справа. Вырежем его и вставим перед <tex>p(x) </tex>.# Если после этого у <tex>p(x)</tex> осталось менее <tex>3</tex> детей, проделаем шаги <tex>1</tex> и <tex>2</tex> и с ними тоже.# Если после этого <tex> p(x) </tex> стал листом, присвоим <tex> rank(p(x)) = 0 </tex> и удалим <tex> p(x) </tex> из <tex>\mathrm{N_{LIST}}</tex> корня дерева.# Если после этого <tex>\mathrm{N_{LIST}}</tex> корня стал пустым (это значит, что дерево стало сокращенным), присвоим <tex> rank(root) = 1 </tex> Очевидно, что <tex>\mathrm{Relink} </tex> выполняется за <tex>O(1)</tex> ==== Операция Find ====Реализуем собственно операцию <tex>\mathrm{Find(a)}</tex>:# Пусть <tex>x</tex> {{---}} вершина дерева, ассоциированная с элементом <tex>a</tex># Пока <tex>p(x) \neq root</tex>, выполняем:## <tex>t = p(x)</tex>## <tex>Relink(x)</tex>## <tex>x = t</tex> === Реализация операции Delete ===Сначала разработаем процедуру удаления узла из дерева, у которого <tex>size(T) \leqslant 4</tex> {{---}} удаление из такого дерева даст нам сокращенное дерево. Назовем эту процедуру <tex>\mathrm{ReducedTreeDelete(a)} </tex>.==== Операция ReducedTreeDelete ====# Если дерево не сокращенное, сделаем его сокращенным, просто переподвесив все вершины к корню. Так как дерево маленькое {{---}} <tex>size(T) \leqslant 4</tex> {{---}} операция выполняется за <tex>O(1)</tex># Если <tex>a</tex> ассоциирован с листом, просто удалим этот лист.# Иначе <tex>a</tex> ассоциирован с корнем: просто поменяем <tex>a</tex> местами с элементом из любого листа (любого сына корня) и удалим этот лист. Теперь подумаем, как удалять элемент из полного дереве размера больше <tex>4</tex>. После удаления дерево должно остаться полным.  Нам необходимо найти некоторый лист дерева, из которого мы удаляем элемент. Реализуем для этого процедуру <tex>\mathrm{FindLeaf(a)}</tex>.==== Операция FindLeaf ====# Пусть элемент <tex>a</tex> ассоциирован с вершиной <tex>x</tex>.# Если <tex>x</tex> {{---}} лист, задача решена.# Если <tex>x</tex> {{---}} корень дерева, то он является первым в <tex>\mathrm{DFS_{LIST}}</tex>. Но при обходе в глубину последняя пройденная вершина всегда является листом, а значит {{---}} вершина, идущая в <tex>\mathrm{DFS_{LIST}}</tex> перед корнем, является листом. Возвращаем ее.# В противном случае:#* Если <tex>x</tex> имеет брата справа {{---}} <tex>r</tex>, то перед тем как обойти <tex>r</tex> поиском в глубину, мы обошли самый правый лист поддерева <tex>x</tex>. Следовательно, нужный нам лист {{---}} <tex>\mathrm{DFS_{LIST}}[r].prev</tex>.#* Иначе <tex>x</tex> имеет брата слева {{---}} <tex>l</tex>, и по аналогичным рассуждениям листом является <tex>\mathrm{DFS_{LIST}}[x].prev</tex>. Итак, мы нашли некоторый лист дерева за <tex>O(1)</tex>. Теперь нам нужно просто уметь его удалять, но так, чтобы инварианты и структура списков сохранялись.==== Операция DeleteLeaf ====Пусть <tex>x</tex> {{---}} удаляемый лист.# Извлекаем <tex>x</tex> из <tex>\mathrm{C_{LIST}} \; p(x) </tex> и из <tex>\mathrm{DFS_{LIST}}</tex># Удаляем узел <tex>x</tex>Следующие <tex>2</tex> шага обеспечивают сохранение полноты дерева# Если <tex>p(x) \neq root(T)</tex>, вызовем <tex>\mathrm{Relink}</tex> для 2 самых правых детей <tex>p(x)</tex># Иначе найдем среди детей <tex>p(x)</tex> узел, не являющийся листом (с помощью <tex>\mathrm{N_{LIST}}</tex>), и вызовем <tex>\mathrm{Relink}</tex> для <tex>3</tex> его самых правых детей. Так как операция <tex>\mathrm{Relink}</tex> сохраняет полноту дерева и выполняется за <tex>O(1)</tex>, <tex>\mathrm{DeleteLeaf}</tex>, очевидно, обладает теми же свойствами. Итак, соберем воедино операцию <tex>\mathrm{Delete(a)}</tex>: ==== Операция Delete ====Пусть элемент <tex>a</tex> ассоциирован с вершиной <tex>x</tex># Если <tex>size(T) \leqslant 4</tex>, вызываем <tex>\mathrm{ReducedTreeDelete(a)}</tex> # Иначе:## <tex>l = \mathrm{FindLeaf(a)} </tex>## Поменяем элементы в <tex>x</tex> и <tex>l</tex> местами.## <tex>\mathrm{DeleteLeaf(l)}</tex> == Анализ ===== Основные положения ===Докажем верхнюю оценку стоимости операции <tex>\mathrm{Find}</tex> в <tex>O(\log {n})</tex>.{{Определение|id=def_value_node|definition=Определим '''значение''' вершины <tex>v</tex> {{---}} <tex>val(v)</tex> {{---}} следующим образом:   <tex dpi='160'>val(v) = \left(\frac{3}{2} \right)^{rank(p(v))} </tex>}}{{Определение|id=def_value_tree|definition='''Значение множества''' <tex>A</tex> {{---}} <tex>VAL(A)</tex> {{---}} сумма значений вершин <tex>T_A</tex>:   <tex>VAL(A) = \sum\limits_{v \in T_A} {val(v)} </tex>}} Нам необходимо доказать, что все определенные нами операции {{---}} <tex>\mathrm{Makeset}</tex>, <tex>\mathrm{Union}</tex>, <tex>\mathrm{Find}</tex> и <tex>\mathrm{Delete}</tex> {{---}} поддерживают следующий инвариант:; Инвариант 3:: <tex>VAL(A) \geqslant 2^{rank(A)} </tex> {{Утверждение |statement=При выполнении '''инварианта 3''' высота дерева не превышает <tex>O(\log {n})</tex>|proof=Так как в <tex>T_A</tex> есть <tex>|A|</tex> вершин и <tex dpi='140'>val(v) \leqslant \left(\frac{3}{2} \right)^{rank(A)}</tex>, то: <center><tex dpi='160'>2^{rank(A)} \leqslant VAL(A) \leqslant |A| \left(\frac{3}{2} \right)^{rank(A)}\newline\newline|A| \geqslant \frac {2^{rank(A)}} {\left(\frac{3}{2} \right)^{rank(A)}} = \left( \frac {4} {3} \right)^{rank(A)}\newline\newlinerank(A) \leqslant \log_{ \frac{4}{3} } { (|A|) } = O(\log {|A|}) = O(\log{n})</tex></center>А так как <tex>h(T_A) \leqslant rank(A)</tex>, утверждение доказано.}} {{Лемма|id=lemma_1|author=1|statement=Для всякого сокращенного дерева <tex>T_A</tex> '''инвариант 3''' выполняется|proof=Если <tex>h(T_A) = 0</tex> (т. е. дерево состоит только из корня), то <tex dpi='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>. Если <tex>h(T_A) = 1</tex>, то <tex dpi='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>}} Докажем теперь, что каждая из операций сохраняет '''инвариант 3'''. === Makeset ===Т. к. операция <tex>\mathrm{Makeset}</tex> создает сокращенное дерево, то по '''лемме 1''' <tex>\mathrm{Makeset}</tex> сохраняет '''инвариант 3''' === Union ===Пусть для множеств <tex>A</tex> и <tex>B</tex> '''инвариант 3''' выполняется. Пусть <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>, и следовательно,  <center><tex>VAL(C) > VAL(A) \geqslant 2^{rank(A)} = 2^{rank(C)}</tex></center> Пусть теперь <tex>rank(A) = rank(B)</tex>, тогда <tex>rank(C) = rank(A) + 1</tex> и имеем:  <center><tex>VAL(C) > VAL(A) + VAL(B) \geqslant 2^{rank(A)} + 2^{rank(B)} = 2^{1 + rank(A)} = 2^{rank(C)} </tex></center> Следовательно, операция <tex>\mathrm{Union}</tex> сохраняет '''инвариант 3'''. === Find ===Пусть для множества <tex>A</tex> '''инвариант 3''' выполняется. Операция <tex>\mathrm{Find}</tex> изменяет дерево <tex>T_A</tex>. Если после выполнения <tex>\mathrm{Find} \; T_A</tex> стало сокращенным, то '''инвариант 3''' сохранен по '''лемме 1'''. Осталось рассмотреть другой случай {{---}} когда до и после выполнения <tex>\mathrm{Find} \; T_A</tex> было полным. Обозначим множество <tex>A</tex> после выполнения <tex>\mathrm{Find}</tex> как <tex>A'</tex> Так как <tex>\mathrm{Find}</tex> изменяет <tex>T_A</tex> только посредством операции <tex>\mathrm{Relink}</tex>, достаточно доказать, что <tex>\mathrm{Relink}</tex> сохраняет '''инвариант 3'''. ==== Анализ операции Relink ====Операция <tex>\mathrm{Relink}</tex> переподвешивает узел <tex>x</tex> к <tex>p(p(x))</tex>. Пусть <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> меняет ранг корня только тогда, когда дерево стало сокращенным, а сейчас мы рассматриваем только полные деревья. Из этого вытекает: <center><tex>VAL(A') \geqslant VAL(A) \geqslant 2^{rank(A)} = 2^{rank(A')}</tex></center> Итак, операция <tex>\mathrm{Relink}</tex> сохраняет '''инвариант 3''', следовательно {{---}} операция <tex>\mathrm{Find}</tex> сохраняет '''инвариант 3'''. === Delete ===Пусть для множества <tex>A</tex> '''инвариант 3''' выполняется. Если после выполнения <tex>\mathrm{Delete} \; T_A</tex> стало сокращенным, то '''инвариант 3''' сохранен по '''лемме 1'''.  Осталось рассмотреть случай, когда до и после выполнения <tex>\mathrm{Delete} \; T_A</tex> было полным. Обозначим множество <tex>A</tex> после выполнения <tex>\mathrm{Delete}</tex> как <tex>A'</tex> Так как операция <tex>\mathrm{FindLeaf}</tex> и обмен элементами между узлами не меняют структуры дерева, достаточно рассмотреть операцию <tex>\mathrm{DeleteLeaf}</tex>. ==== Анализ операции DeleteLeaf ====Пусть <tex>x</tex> {{---}} удаляемый элемент, <tex>y = p(x)</tex>.* Если <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> его братьев, их суммарное значение не больше <tex dpi='140'>3 \left( \frac {3} {2} \right) ^ {k - 1} </tex>. Потом мы подвешиваем <tex>2</tex> братьев к <tex>g</tex> {{---}} их суммарное значение становится <tex dpi='140'>2 \left( \frac {3} {2} \right) ^ k </tex>. Итого, суммарное изменение значения не меньше <center><tex dpi='140'>-3 \left( \frac {3} {2} \right) ^ {k - 1} + 2 \left( \frac {3} {2} \right) ^ k = 0</tex>,</center> следовательно,<center><tex>VAL(A') \geqslant VAL(A)</tex></center> <tex>\mathrm{Delete} </tex> меняет <tex> rank(A) </tex> только когда дерево становится сокращенным, а мы рассматриваем только полные, следовательно {{---}} <tex> rank(A) </tex> не меняется, следовательно: <center><tex>VAL(A') \geqslant VAL(A) \geqslant 2^{rank(A)} = 2^{rank(A')}</tex></center>  * Если Если <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>, следовательно суммарное значение дерева сначала убывает на не более чем <tex dpi='140'>\left( \frac {3} {2} \right) ^ k + 3 \left( \frac {3} {2} \right) ^ {k - 1}</tex> а после увеличивается на <tex dpi='140'>3 \left( \frac {3} {2} \right) ^ k </tex>. Итого, суммарное изменение значения не меньше чем<center><tex dpi='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)</tex>,</center>а так как <tex>2^{rank(A)} = 2^{rank(A')}</tex>, то<center><tex>VAL(A') \geqslant VAL(A) \geqslant 2^{rank(A)} = 2^{rank(A')}</tex></center>  Итак, операция <tex>\mathrm{DeleteLeaf}</tex> сохраняет '''инвариант 3''', а значит, и операция <tex>\mathrm{Delete} </tex> сохраняет его. === Выводы ==={{Лемма|id=lemma_2|statement=В вышеописанной структуре данных '''инвариант 3''' сохраняется до и после каждой операции|proof=Изначально дерево является сокращенным и '''инвариант 3''' выполняется в нем по '''лемме 1'''; каждая последующая операция сохраняет инвариант {{---}} лемма доказана.}}; Следствие 1: Высота дерева никогда не превышает <tex>O(\log {n})</tex>, следовательно операция <tex>\mathrm{Find}</tex> занимает <tex>O(\log {n})</tex> в худшем случае.; Следствие 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][[Категория: Дискретная математика и алгоритмы]] [[Категория: Система непересекающихся множеств ]]