СНМ с операцией удаления за О(1) — различия между версиями

Текущая версия на 19:40, 4 сентября 2022

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

Описание

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

[math]\mathrm {Makeset(x)}[/math] — создать новое множество из [math]1[/math] элемента [math]x[/math]. Время: [math]O(1)[/math].
[math]\mathrm {Union(A, B)}[/math] — объединить множества [math]A[/math] и [math]B[/math] в одно. Время: [math] O(1) [/math], без учета времени на операцию [math]\mathrm{Find}[/math], которая используется, если множества [math]A[/math] и [math]B[/math] заданы своими произвольными представителями.
[math]\mathrm {Find(x)}[/math] — найти множество, в котором содержится элемент [math] x [/math]. Время: [math]O(\log {n})[/math] в худшем случае, [math]O(\alpha(n))[/math] — в среднем ([math]\alpha(n)[/math] — обратная функция Аккермана), где [math] n [/math] — размер множества.
[math]\mathrm{Delete(x)}[/math] — удалить элемент x из содержащего его множества. Время: [math]O(1)[/math].

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

[math]size(A)[/math] — размер множества [math]A[/math] (количество элементов в нем).
[math]root(T_A)[/math] — корень дерева [math]T_A[/math].
[math]h(v)[/math] — высота вершины [math]v[/math]: если [math]v[/math] является листом, то [math]h(v) = 0[/math], иначе .
[math]p(v)[/math] — родитель вершины [math]v[/math]. Если [math]v[/math] — корень, то считаем, что [math]p(v) = v[/math].
[math]rank(v)[/math] — ранг вершины, некоторая верхняя оценка на ее высоту.

Как и в реализации с помощью леса корневых деревьев, выполнено следующее: [math]rank(v) \lt rank(p(v))[/math].

Идея

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

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

Соображение 2: Пусть есть возможность находить какой-нибудь лист (неважно, какой именно) в дереве за [math]O(1)[/math]. Тогда, по соображению 1, мы уже умеем удалять произвольный элемент из дерева за [math]O(1)[/math].

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

Реализация

Расширение структуры данных

Расширим лес корневых деревьев следующим образом:

Модификации для 1-го соображения

Разделим понятия вершина дерева и элемент множества:

вершиной дерева назовем объект, содержащий ссылки [math]next[/math], [math]prev[/math] и [math]head[/math] (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине элемент множества;
элемент множества — объект, содержащий значение элемента и ссылку на соотв. вершину дерева.

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

Модификации для 2-го соображения

Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список [math] \mathrm{C_{LIST}} [/math] ее детей. Будем считать, что дети упорядочены по направлению списка слева направо.
Для корня каждого дерева храним двусвязный список [math] \mathrm{N_{LIST}} [/math] его детей, не являющихся листьями.
Для каждого дерева (включая поддеревья) храним циклический двусвязный список [math] \mathrm{DFS_{LIST}} [/math] его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.

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

Введем также следующие определения:

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

Дерево, либо состоящее ровно из одной вершины, либо же из вершины ранга и листьев ранга , называется сокращенным (англ. reduced).

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

Дерево называется полным (англ. full), если каждый из его узлов либо является листом с рангом , либо имеет не менее детей.

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

Все деревья (и поддеревья) размера [math]\lt 4[/math] — сокращенные, а [math]\geqslant 4[/math] — полные
Каждая вершина, среди детей которой есть хотя бы [math]1[/math] нелистовая вершина, имеет не менее [math]3[/math] детей (это не позволяет дереву вытягиваться в бамбук, например)

Реализация операции Makeset

Тривиально:

Создадим узел [math]v[/math] и свяжем его с элементом [math]x[/math]. Установим: [math]p(v) = v, rank(v) = 0[/math].
Создадим для вершины [math]v[/math] пустые списки [math]\mathrm{N_{LIST}}[/math] и [math]\mathrm{C_{LIST}}[/math].
Создадим [math]\mathrm{DFS_{LIST}}[/math] с одним элементом — вершина [math]v[/math].

Очевидно, что операция соблюдает инварианты и выполняется за [math]O(1)[/math].

Реализация операции Union

Пусть [math] T_A, T_B [/math] — деревья, реализующие множества [math]A[/math] и [math]B[/math] соответственно. Пусть размер одного из деревьев меньше [math]4[/math]; не умаляя общности — [math]size(T_B) \lt 4[/math]. Тогда действуем следующим образом:

.
.
Присоединим [math]\mathrm{ DFS_{LIST}} [/math] и [math]\mathrm{C_{LIST}}[/math] для [math]T_B [/math] в конец [math]\mathrm{ DFS_{LIST}} [/math] и [math]\mathrm{C_{LIST}}[/math] для [math]T_A[/math].

Теперь рассмотрим случай, когда размеры обоих деревьев больше [math]4[/math]. Примем, не умаляя общности, что . Тогда:

[math]p(root(T_B)) = root(T_A)[/math], и если , увеличим [math]rank(root(T_A))[/math] на [math]1[/math].
Вставим [math]root(T_B)[/math] в начало [math]\mathrm{ N_{LIST}} [/math] и [math]\mathrm{C_{LIST}}[/math] для [math]T_A[/math].
Вставим [math]\mathrm{ DFS_{LIST}} [/math] для [math]T_B [/math] в [math]\mathrm{ DFS_{LIST}} [/math] для [math]T_A [/math] сразу после [math]root(T_A)[/math].
Сделаем [math]\mathrm{ N_{LIST}} [/math] для [math]T_B [/math] пустым. (Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную)

Если в качестве идентификаторов множеств нам переданы произвольные представители этих множеств, нам придется запустить процедуру [math]\mathrm {Find}[/math] для каждого из них, чтобы найти корни деревьев. Без учета вызова процедуры [math]\mathrm {Find}[/math] мы сделаем [math]O(1)[/math] операций.

Реализация операции Find

В нашей реализации операции [math]\mathrm {Find}[/math] вместо уже известного метода сжатия путей (англ. path compressing) будем использовать разделение путей (англ. path splitting). Он заключается в том, чтобы при выполнении операции [math]\mathrm {Find}[/math] перевешивать элемент, от которого мы вызвались, не сразу к корню, а к собственному "дедушке". Такой метод сокращения пути приводит к той же амотризационной оценке для функции [math]\mathrm {Find}[/math]^[1], несмотря на то, что интуитивно кажется более медленным. Мы будем использовать именно разделение путей, потому что это серьезно упрощает поддержку списков и инвариантов.

Операция Relink

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

Удалим [math] x [/math] из [math] \mathrm{C_{LIST}} \; p(x)[/math] и вставим его в [math] \mathrm{C_{LIST}} \; p(p(x))[/math] следующим образом:
- Если [math]x[/math] имеет брата справа от себя, вставим его в сразу слева от [math] p(x) [/math]
- Иначе (если [math] x [/math] — крайний правый сын [math]p(x)[/math]) — вставим [math] x [/math] сразу справа от [math] p(x) [/math]
Обновим [math] \mathrm {DFS_{LIST}} [/math] следующим образом:
- Если [math]x[/math] — крайний правый сын [math]p(x)[/math], то на предыдущем шаге мы вставили его в список детей [math]p(p(x))[/math] сразу после [math]p(x)[/math], следовательно — порядок обхода вершин из [math] p(p(x)) [/math] в глубину не изменился. Значит, нам не нужно менять [math] \mathrm {DFS_{LIST}} [/math].
- В противном случае нам нужно поместить участок [math] \mathrm {DFS_{LIST}} [/math], соответствующий поддереву [math]x[/math], перед [math]p(x) [/math]. Этот участок — полуинтервал [math][x, l)[/math], где [math]l[/math] — сосед [math]x[/math] справа. Вырежем его и вставим перед [math]p(x) [/math].
Если после этого у [math]p(x)[/math] осталось менее [math]3[/math] детей, проделаем шаги [math]1[/math] и [math]2[/math] и с ними тоже.
Если после этого [math] p(x) [/math] стал листом, присвоим [math] rank(p(x)) = 0 [/math] и удалим [math] p(x) [/math] из [math]\mathrm{N_{LIST}}[/math] корня дерева.
Если после этого [math]\mathrm{N_{LIST}}[/math] корня стал пустым (это значит, что дерево стало сокращенным), присвоим [math] rank(root) = 1 [/math]

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

Операция Find

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

Пусть [math]x[/math] — вершина дерева, ассоциированная с элементом [math]a[/math]
Пока [math]p(x) \neq root[/math], выполняем:
1. [math]t = p(x)[/math]
2. [math]Relink(x)[/math]
3. [math]x = t[/math]

Реализация операции Delete

Сначала разработаем процедуру удаления узла из дерева, у которого [math]size(T) \leqslant 4[/math] — удаление из такого дерева даст нам сокращенное дерево. Назовем эту процедуру .

Операция ReducedTreeDelete

Если дерево не сокращенное, сделаем его сокращенным, просто переподвесив все вершины к корню. Так как дерево маленькое — [math]size(T) \leqslant 4[/math] — операция выполняется за [math]O(1)[/math]
Если [math]a[/math] ассоциирован с листом, просто удалим этот лист.
Иначе [math]a[/math] ассоциирован с корнем: просто поменяем [math]a[/math] местами с элементом из любого листа (любого сына корня) и удалим этот лист.

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

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

Операция FindLeaf

Пусть элемент [math]a[/math] ассоциирован с вершиной [math]x[/math].
Если [math]x[/math] — лист, задача решена.
Если [math]x[/math] — корень дерева, то он является первым в [math]\mathrm{DFS_{LIST}}[/math]. Но при обходе в глубину последняя пройденная вершина всегда является листом, а значит — вершина, идущая в [math]\mathrm{DFS_{LIST}}[/math] перед корнем, является листом. Возвращаем ее.
В противном случае:
- Если [math]x[/math] имеет брата справа — [math]r[/math], то перед тем как обойти [math]r[/math] поиском в глубину, мы обошли самый правый лист поддерева [math]x[/math]. Следовательно, нужный нам лист — .
- Иначе [math]x[/math] имеет брата слева — [math]l[/math], и по аналогичным рассуждениям листом является .

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

Операция DeleteLeaf

Пусть [math]x[/math] — удаляемый лист.

Извлекаем [math]x[/math] из [math]\mathrm{C_{LIST}} \; p(x) [/math] и из [math]\mathrm{DFS_{LIST}}[/math]
Удаляем узел [math]x[/math]

Следующие [math]2[/math] шага обеспечивают сохранение полноты дерева

Если [math]p(x) \neq root(T)[/math], вызовем [math]\mathrm{Relink}[/math] для 2 самых правых детей [math]p(x)[/math]
Иначе найдем среди детей [math]p(x)[/math] узел, не являющийся листом (с помощью [math]\mathrm{N_{LIST}}[/math]), и вызовем [math]\mathrm{Relink}[/math] для [math]3[/math] его самых правых детей.

Так как операция [math]\mathrm{Relink}[/math] сохраняет полноту дерева и выполняется за [math]O(1)[/math], [math]\mathrm{DeleteLeaf}[/math], очевидно, обладает теми же свойствами.

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

Операция Delete

Пусть элемент [math]a[/math] ассоциирован с вершиной [math]x[/math]

Если [math]size(T) \leqslant 4[/math], вызываем
Иначе:
1. [math]l = \mathrm{FindLeaf(a)} [/math]
2. Поменяем элементы в [math]x[/math] и [math]l[/math] местами.
3. [math]\mathrm{DeleteLeaf(l)}[/math]

Анализ

Основные положения

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

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

Определим значение вершины — — следующим образом:

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

Значение множества — — сумма значений вершин :

Нам необходимо доказать, что все определенные нами операции — [math]\mathrm{Makeset}[/math], [math]\mathrm{Union}[/math], [math]\mathrm{Find}[/math] и [math]\mathrm{Delete}[/math] — поддерживают следующий инвариант:

Инвариант 3

Утверждение:

При выполнении инварианта 3 высота дерева не превышает

Так как в [math]T_A[/math] есть [math]|A|[/math] вершин и , то:

А так как , утверждение доказано.

Лемма (1):

Для всякого сокращенного дерева инвариант 3 выполняется

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

Если [math]h(T_A) = 0[/math] (т. е. дерево состоит только из корня), то и .

Если , то и

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

Makeset

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

Union

Пусть для множеств [math]A[/math] и [math]B[/math] инвариант 3 выполняется.

Пусть [math]C = \mathrm{Union(A, B)}[/math]. Пусть, не умаляя общности, [math]rank(A) \gt rank(B)[/math]. Тогда мы подвесим [math]T_B[/math] к корню [math]T_A[/math], и [math]rank(C)[/math] будет равным [math]rank(A)[/math], и следовательно,

Пусть теперь [math]rank(A) = rank(B)[/math], тогда [math]rank(C) = rank(A) + 1[/math] и имеем:

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

Find

Пусть для множества [math]A[/math] инвариант 3 выполняется.

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

Осталось рассмотреть другой случай — когда до и после выполнения [math]\mathrm{Find} \; T_A[/math] было полным. Обозначим множество [math]A[/math] после выполнения [math]\mathrm{Find}[/math] как [math]A'[/math]

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

Анализ операции Relink

Операция [math]\mathrm{Relink}[/math] переподвешивает узел [math]x[/math] к [math]p(p(x))[/math].

Пусть . Следовательно, до переподвешивания , а после переподвешивания . Таким образом, при переподвешивании [math]x \; VAL(A)[/math] может только увеличиться. Тем временем [math]rank(A)[/math] остается неизменным, ведь [math]\mathrm{Relink}[/math] меняет ранг корня только тогда, когда дерево стало сокращенным, а сейчас мы рассматриваем только полные деревья. Из этого вытекает:

Итак, операция [math]\mathrm{Relink}[/math] сохраняет инвариант 3, следовательно — операция [math]\mathrm{Find}[/math] сохраняет инвариант 3.

Delete

Пусть для множества [math]A[/math] инвариант 3 выполняется.

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

Осталось рассмотреть случай, когда до и после выполнения [math]\mathrm{Delete} \; T_A[/math] было полным. Обозначим множество [math]A[/math] после выполнения [math]\mathrm{Delete}[/math] как [math]A'[/math]

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

Анализ операции DeleteLeaf

Пусть [math]x[/math] — удаляемый элемент, [math]y = p(x)[/math].

Если [math]y \neq root[/math], то обозначим . Мы удаляем [math]x[/math] и отсоединяем [math]2[/math] его братьев, их суммарное значение не больше . Потом мы подвешиваем [math]2[/math] братьев к [math]g[/math] — их суммарное значение становится . Итого, суммарное изменение значения не меньше

,

следовательно,

[math]\mathrm{Delete} [/math] меняет [math] rank(A) [/math] только когда дерево становится сокращенным, а мы рассматриваем только полные, следовательно — [math] rank(A) [/math] не меняется, следовательно:

Если Если [math]y = root[/math], то обозначим . Обозначим некоторого брата [math]x[/math], не являющегося листом, как . Мы удаляем [math]x[/math] и переподвешиваем [math]3[/math] сыновей [math]c[/math], следовательно суммарное значение дерева сначала убывает на не более чем а после увеличивается на . Итого, суммарное изменение значения не меньше чем

,

следовательно

,

а так как [math]2^{rank(A)} = 2^{rank(A')}[/math], то

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

Выводы

Лемма:

В вышеописанной структуре данных инвариант 3 сохраняется до и после каждой операции

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

Изначально дерево является сокращенным и инвариант 3 выполняется в нем по лемме 1; каждая последующая операция сохраняет инвариант — лемма доказана.

Следствие 1: Высота дерева никогда не превышает [math]O(\log {n})[/math], следовательно операция [math]\mathrm{Find}[/math] занимает [math]O(\log {n})[/math] в худшем случае.
Следствие 2: [math]\mathrm{Find}[/math] занимает [math]O(\alpha (n))[/math] в среднем^[2].

Примечания

Источники информации

A. Ben-Amram, S. Yoﬀe. A Simple And Efficient Union-Find-Delete Algorithm

[1] Robert E. Tarjan and Jan van Leeuwen. Worst-case analysis of set union algorithms. Journal of the ACM, 31(2):245–281, 1984.

[2] S. Alstrup, I. L. Gørtz, T. Rauhe, M. Thorup, and U. Zwick. Union-ﬁnd with constant time deletions.

[1]

[2]

СНМ с операцией удаления за О(1) — различия между версиями

Текущая версия на 19:40, 4 сентября 2022

Содержание

Описание

Идея

Реализация

Расширение структуры данных

Модификации для 1-го соображения

Модификации для 2-го соображения

Реализация операции Makeset

Реализация операции Union

Реализация операции Find

Операция Relink

Операция Find

Реализация операции Delete

Операция ReducedTreeDelete

Операция FindLeaf

Операция DeleteLeaf

Операция Delete

Анализ

Основные положения

Makeset

Union

Find

Анализ операции Relink

Delete

Анализ операции DeleteLeaf

Выводы

Примечания

Источники информации

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты

@@ Строка 1: / Строка 1: @@
-Реализация системы непересекающихся множеств с помощью [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|леса корневых деревьев]] не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за О(1) в худшем случае, сохраняя асимптотику для операций Union и Find и потребление памяти O(n).
+Реализация системы непересекающихся множеств с помощью [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|леса корневых деревьев]] не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за истинную <tex>O(1)</tex>, сохраняя асимптотику для операций <tex>\mathrm{ Union } </tex> и <tex>\mathrm{Find}</tex> и потребление памяти <tex>O(n)</tex>.
-== Введение ==
+== Описание ==
-Наша структура данных должна поддерживать следующие операции:
+Структура данных должна поддерживать следующие операции:
-* <tex>makeset(x)</tex> - создать новое множество из 1 элемента <tex>x </tex>. Время: <tex>O(1)</tex>
+* <tex>\mathrm {Makeset(x)}</tex> {{---}} создать новое множество из <tex>1</tex> элемента <tex>x</tex>. Время: <tex>O(1)</tex>.
-* <tex>union(A, B)</tex> - объединить множества A и B в одно. Время: <tex> O(1) </tex>, без учета времени на операцию <tex>find</tex>, которая используется, если множества A и B заданы своими произвольными представителями.
+* <tex>\mathrm {Union(A, B)}</tex> {{---}} объединить множества <tex>A</tex> и <tex>B</tex> в одно. Время: <tex> O(1) </tex>, без учета времени на операцию <tex>\mathrm{Find}</tex>, которая используется, если множества <tex>A</tex> и <tex>B</tex> заданы своими произвольными представителями.
-* <tex>find(x)</tex> - найти множество, в котором содержится элемент <tex> x </tex>. Время; <tex>O(log n)</tex> в худшем случае, <tex>O(\alpha(n))</tex> - в среднем (<tex>\alpha(n)</tex> - обратная функция Аккермана), где n - размер множества.
+* <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>delete(x)</tex> - удалить элемент x из содержащего его множества. Время: O(1)
+* <tex>\mathrm{Delete(x)}</tex> {{---}} удалить элемент x из содержащего его множества. Время: <tex>O(1)</tex>.
-В дальнейшем мы будем использовать следующие понятия и обозначения:
+В дальнейшем используются следующие понятия и обозначения:
-* <tex>size(A)</tex> - размер множества A (количество элементов в нем).
+* <tex>size(A)</tex> {{---}} размер множества <tex>A</tex> (количество элементов в нем).
-* <tex>root(T_A)</tex> - корень дерева <tex>T_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 \} </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>p(v)</tex> {{---}} родитель вершины <tex>v</tex>. Если <tex>v</tex> {{---}} корень, то считаем, что <tex>p(v) = v</tex>.
-* <tex>rank(v)</tex> - ранг вершины, некоторая верхняя оценка на ее высоту.
+* <tex>rank(v)</tex> {{---}} ранг вершины, некоторая верхняя оценка на ее высоту.
-Как и в [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|обычной реализации]], выполнено следующее: <tex>rank(v) < rank(p(v))</tex>
+Как и в [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|реализации с помощью леса корневых деревьев]], выполнено следующее: <tex>rank(v) < rank(p(v))</tex>.
 == Идея ==
-В реализации СНМ с помощью леса корневых деревьев мы не можем удалить произвольную вершину из множества за разумное время - в таком случае нам придется переподвешивать <tex>O(n) </tex> поддеревьев этой вершины. Однако, если вершина является листом, то ее можно удалять совершенно безболезненно. <br />
+В реализации СНМ с помощью леса корневых деревьев нет возможности удалить произвольную вершину из множества за разумное время {{---}} в таком случае придется переподвешивать <tex>O(n) </tex> поддеревьев этой вершины. Однако, если вершина является листом, то ее можно удалять совершенно безболезненно.
-'''Соображение 1:''' Пусть мы умеем менять произвольные вершины местами за <tex>O(1)</tex>. Тогда для удаления некоторой вершины достаточно поменять ее местами с каким-нибудь листом и удалить этот лист. <br />
-'''Соображение 2:''' Пусть мы умеем находить какой-нибудь лист (неважно, какой именно) в дереве за <tex>O(1)</tex>. Тогда, по соображению 1, мы уже умеем удалять произвольный элемент из дерева за <tex>O(1)</tex>
+;Соображение 1 : Пусть есть возможность менять произвольные вершины местами за <tex>O(1)</tex>. Тогда для удаления некоторой вершины достаточно поменять ее местами с каким-нибудь листом и удалить этот лист.
-<br />
-Все дальнейшие действия направлены на то, чтобы поддержать эти 2 операции, не испортив при этом асимптотику всех остальных.
+;Соображение 2 : Пусть есть возможность находить какой-нибудь лист (неважно, какой именно) в дереве за <tex>O(1)</tex>. Тогда, по '''соображению 1''', мы уже умеем удалять произвольный элемент из дерева за <tex>O(1)</tex>.
+Все дальнейшие усилия направлены на то, чтобы поддержать эти <tex>2</tex> операции, не испортив при этом асимптотику всех остальных.
 == Реализация ==
 === Расширение структуры данных ===
 Расширим [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|лес корневых деревьев]] следующим образом:
-* Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список <tex> \mathrm{C_{list}} </tex> ее детей. Будем считать, что дети упорядочены по направлению списка слева направо.
+==== Модификации для 1-го соображения ====
-* Для корня каждого дерева храним двусвязный список <tex> \mathrm{NL_{list}} </tex> его детей, не являющихся листьями.
+Разделим понятия '''вершина дерева''' и '''элемент множества''':
-* Для каждого дерева (включая поддеревья) храним циклический двусвязный список <tex> \mathrm{DFS_{list}} </tex> его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.
+* '''вершиной дерева''' назовем объект, содержащий ссылки <tex>next</tex>, <tex>prev</tex> и <tex>head</tex> (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине '''элемент множества''';
-* Разделим понятия '''вершина дерева''' и '''элемент множества''':
+* '''элемент множества''' {{---}} объект, содержащий значение элемента и ссылку на соотв. '''вершину дерева'''.
-** '''вершиной дерева''' назовем объект, содержащий ссылки <tex>next</tex>, <tex>prev</tex> и <tex>head</tex> (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине '''элемент множества''';
+Это нововведение, очевидно, позволит менять элементы в дереве местами за <tex>O(1)</tex>.
-** '''элемент множества''' - объект, содержащий значение элемента и ссылку на соотв. '''вершину дерева'''.
-<br />
+==== Модификации для 2-го соображения ====
-Последнее нововведение, очевидно, позволит нам менять элементы в дереве местами за <tex>O(1)</tex>. <br />
+* Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список <tex> \mathrm{C_{LIST}} </tex> ее детей. Будем считать, что дети упорядочены по направлению списка слева направо.
-Первые три необходимы для нахождения листа в дереве (как оказывается, это гораздо более нетривиальная задача)
+* Для корня каждого дерева храним двусвязный список <tex> \mathrm{N_{LIST}} </tex> его детей, не являющихся листьями.
-<br/>
+* Для каждого дерева (включая поддеревья) храним циклический двусвязный список <tex> \mathrm{DFS_{LIST}} </tex> его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.
+Эти три нововведения необходимы для нахождения листа в дереве (как оказывается, это гораздо более нетривиальная задача).
 Введем также следующие определения:
 {{Определение
 |id=def_reduced_tree
-|definition=Дерево, либо состоящее ровно из одной вершины, либо же из 1 вершины ранга 1 и листьев ранга 0, называется '''сокращенным''' (''reduced'')
+|definition=Дерево, либо состоящее ровно из одной вершины, либо же из <tex>1</tex> вершины ранга <tex>1</tex> и листьев ранга <tex>0</tex>, называется '''сокращенным''' (англ. ''reduced'').
 }}
 {{Определение
 |id=def_full_tree
-|definition=Дерево называется '''полным''', если каждый из его узлов либо является листом с рангом 0, либо имеет не менее 3 детей.
+|definition=Дерево называется '''полным''' (англ. ''full''), если каждый из его узлов либо является листом с рангом <tex>0</tex>, либо имеет не менее <tex>3</tex> детей.
 }}
 В нашей структуре данных будет поддерживаться следующий инвариант: '''дерево всегда полное или сокращенное'''.
 Этот инвариант влечет за собой очевидные следствия:
-* Все деревья (и поддеревья) размера < 4 - сокращенные, а >= 4 - полные
+* Все деревья (и поддеревья) размера <tex>< 4</tex> {{---}} сокращенные, а <tex>\geqslant 4</tex> {{---}} полные
-* Каждая вершина, среди детей которой есть хотя бы 1 нелистовая вершина, имеет не менее 3 детей (это не позволяет дереву вытягиваться в бамбук, например)
+* Каждая вершина, среди детей которой есть хотя бы <tex>1</tex> нелистовая вершина, имеет не менее <tex>3</tex> детей (это не позволяет дереву вытягиваться в бамбук, например)
 === Реализация операции Makeset ===
 Тривиально:
-# Создадим узел <tex>v</tex> и свяжем его с элементом <tex>x</tex>. Установим: <tex>p(v) \leftarrow v, rank(v) \leftarrow 0</tex>
+# Создадим узел <tex>v</tex> и свяжем его с элементом <tex>x</tex>. Установим: <tex>p(v) = v, rank(v) = 0</tex>.
-# Создадим для вершины <tex>v</tex> пустые списки <tex>\mathrm{NL_{LIST}}</tex> и <tex>\mathrm{C_{LIST}}</tex>.
+# Создадим для вершины <tex>v</tex> пустые списки <tex>\mathrm{N_{LIST}}</tex> и <tex>\mathrm{C_{LIST}}</tex>.
-# Создадим <tex>\mathrm{DFS_{LIST}}</tex> с одним элементом - вершина <tex>v</tex>
+# Создадим <tex>\mathrm{DFS_{LIST}}</tex> с одним элементом {{---}} вершина <tex>v</tex>.
-Очевидно, что операция соблюдает инварианты и выполняется за <tex>O(1)</tex>
+Очевидно, что операция соблюдает инварианты и выполняется за <tex>O(1)</tex>.
 === Реализация операции Union ===
-Пусть <tex> T_A, T_B </tex> - деревья, реализующие множества <tex>A</tex> и <tex>B</tex> соответственно.
+Пусть <tex> T_A, T_B </tex> {{---}} деревья, реализующие множества <tex>A</tex> и <tex>B</tex> соответственно.
-Пусть размер одного из деревьев меньше 4; не умаляя общности - <tex>size(T_B) < 4</tex>. Тогда действуем следующим образом:
+Пусть размер одного из деревьев меньше <tex>4</tex>; не умаляя общности {{---}} <tex>size(T_B) < 4</tex>. Тогда действуем следующим образом:
-# <tex>\forall v \in T_B : \: p(v) \leftarrow root(T_A), \: rank(v) \leftarrow 0</tex>
+# <tex>\forall v \in T_B : \: p(v) = root(T_A), \: rank(v) = 0</tex>.
-# <tex> rank(root(T_A)) \leftarrow max \: \{ rank(root(T_A)), 1 \: \}</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>\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>.
-Теперь рассмотрим случай, когда размеры обоих деревьев больше 4.
+Теперь рассмотрим случай, когда размеры обоих деревьев больше <tex>4</tex>.
-Примем, не умаляя общности, что <tex>rank(root(T_A)) \geq rank(root(T_B))</tex>. Тогда:
+Примем, не умаляя общности, что <tex>rank(root(T_A)) \geqslant rank(root(T_B))</tex>. Тогда:
-#  <tex>p(root(T_B)) \leftarrow root(T_A)</tex>, и если <tex>rank(root(T_A)) = rank(root(T_B))</tex>, увеличим <tex>rank(root(T_A))</tex> на 1.
+#  <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>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{ 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>find</tex> для каждого из них, чтобы найти корни деревьев.
+Если в качестве идентификаторов множеств нам переданы произвольные представители этих множеств, нам придется запустить процедуру <tex>\mathrm {Find}</tex> для каждого из них, чтобы найти корни деревьев.
-Без учета вызова процедуры <tex>find</tex> мы сделаем O(1) операций.
+Без учета вызова процедуры <tex>\mathrm {Find}</tex> мы сделаем <tex>O(1)</tex> операций.
 === Реализация операции Find ===
-В нашей реализации операции <tex>find</tex> вместо уже известного нам метода '''сжатия путей (path compressing)''' мы будем использовать '''разделение путей (path splitting)'''. Он заключается в том, чтобы при выполнении операции find перевешивать элемент, от которого мы вызвались, не сразу к корню, а к собственному "дедушке". Такой метод сокращения пути приводит к той же амотризационной оценке для функции <tex>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>, несмотря на то, что интуитивно кажется более медленным. Мы будем использовать именно разделение путей, потому что это серьезно упрощает поддержку списков и инвариантов.
+В нашей реализации операции <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'>
+^{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
+\newline
+rank(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-ﬁnd with constant time deletions.]</ref>.
 == Примечания ==
 <references />
-== Ссылки ==
+== Источники информации ==
-* [http://www2.mta.ac.il/~amirben/downloadable/ufd.pdf A Simple And Efficient Union-Find-Delete Algorithm]
+* [http://www2.mta.ac.il/~amirben/downloadable/ufd.pdf A. Ben-Amram, S. Yoﬀe. A Simple And Efficient Union-Find-Delete Algorithm]
+[[Категория: Дискретная математика и алгоритмы]]
+[[Категория: Система непересекающихся множеств ]]