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

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

Введение

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

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

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

• [math]size(A)[/math] — размер множества A (количество элементов в нем).
• [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]h(v) = max \{ h(w) \: | \: w - \mathrm{ child \: of } \: v \} [/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]

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

Реализация

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

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

• Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список [math] \mathrm{C_{list}} [/math] ее детей. Будем считать, что дети упорядочены по направлению списка слева направо.
• Для корня каждого дерева храним двусвязный список [math] \mathrm{NL_{list}} [/math] его детей, не являющихся листьями.
• Для каждого дерева (включая поддеревья) храним циклический двусвязный список [math] \mathrm{DFS_{list}} [/math] его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.
• Разделим понятия вершина дерева и элемент множества:
  • вершиной дерева назовем объект, содержащий ссылки [math]next[/math], [math]prev[/math] и [math]head[/math] (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине элемент множества;
  • элемент множества - объект, содержащий значение элемента и ссылку на соотв. вершину дерева.

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

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

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

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

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

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

• Все деревья (и поддеревья) размера < 4 - сокращенные, а >= 4 - полные
• Каждая вершина, среди детей которой есть хотя бы 1 нелистовая вершина, имеет не менее 3 детей (это не позволяет дереву вытягиваться в бамбук, например)

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

Тривиально:

1. Создадим узел [math]v[/math] и свяжем его с элементом [math]x[/math]. Установим: [math]p(v) := v, rank(v) := 0[/math]
2. Создадим для вершины [math]v[/math] пустые списки [math]\mathrm{NL_{LIST}}[/math] и [math]\mathrm{C_{LIST}}[/math].
3. Создадим [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] соответственно. Пусть размер одного из деревьев меньше 4; не умаляя общности — [math]size(T_B) \lt 4[/math]. Тогда действуем следующим образом:

1. [math]\forall v \in T_B : \: p(v) := root(T_A), \: rank(v) := 0[/math]
2. [math] rank(root(T_A)) := max \: \{ rank(root(T_A)), 1 \: \}[/math]
3. Присоединим [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]

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

1. [math]p(root(T_B)) := root(T_A)[/math], и если [math]rank(root(T_A)) = rank(root(T_B))[/math], увеличим [math]rank(root(T_A))[/math] на 1.
2. Вставим [math]root(T_B)[/math] в начала [math]\mathrm{ N_{LIST}} [/math] и [math]\mathrm{C_{LIST}}[/math] для [math]T_A[/math]
3. Вставим [math]\mathrm{ DFS_{LIST}} [/math] для [math]T_B [/math] в [math]\mathrm{ DFS_{LIST}} [/math] для [math]T_A [/math] сразу после [math]root(T_A)[/math]
4. Сделаем [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], несмотря на то, что интуитивно кажется более медленным. Мы будем использовать именно разделение путей, потому что это серьезно упрощает поддержку списков и инвариантов.

Операция Relink

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

1. Удалим [math] x [/math] из [math] \mathrm{C_{LIST}} \; p(x)[/math] и вставим его в [math] \mathrm{C_{LIST}} \; p(p(x))[/math] следующим образом:
   • Если [math]x[/math] имеет брата справа от себя, вставим его в [math] \mathrm{C_{LIST}} \; p(p(x))[/math] сразу слева от [math] p(x) [/math]
   • Иначе (если [math] x [/math] — крайний правый сын [math]p(x)[/math]) — вставим [math] x [/math] сразу справа от [math] p(x) [/math]
2. Обновим [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].
3. Если после этого у [math]p(x)[/math] осталось менее 3 детей, проделаем шаги 1 и 2 и с ними тоже.
4. Если после этого [math] p(x) [/math] стал листом, присвоим [math] rank(p(x)) := 0 [/math] и удалим [math] p(x) [/math] из [math]\mathrm{NL_{LIST}}[/math] корня дерева.
5. Если после этого [math]\mathrm{NL_{LIST}}[/math] корня стал пустым (это значит, что дерево стало сокращенным), присвоим [math] rank(root) := 1 [/math]

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

Операция Find

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

1. Пусть [math]x[/math] — вершина дерева, ассоциированная с элементом [math]a[/math]
2. Пока [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) \leq 4[/math] — удаление из такого дерева даст нам сокращенное дерево. Назовем эту процедуру [math]\mathrm{ReducedTreeDelete(a)} [/math].

Операция ReducedTreeDelete

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

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

Операция FindLeaf

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

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

Операция DeleteLeaf

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

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

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

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

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

Операция Delete

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

1. Если [math]size(T) \leq 4[/math], вызываем [math]\mathrm{ReducedTreeDelete(a)}[/math]
2. Иначе:
   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]v[/math] — [math]val(v)[/math] — следующим образом: [math]val(v) = \left(\frac{3}{2} \right)^{rank(p(v))} [/math]

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

Значение множества [math]A[/math] — [math]VAL(A)[/math] — сумма значений вершин [math]T_A[/math]: [math]VAL(A) = \sum\limits_{v \in T_A} {val(v)} [/math]

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

Инвариант 3

[math]VAL(A) \geq 2^{rank(A)} [/math]

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

При выполнении инварианта 3 высота дерева не превышает [math]O(\log {n})[/math]

[math]\triangleright[/math]

Так как в [math]T_A[/math] есть [math]|A|[/math] вершин и [math]val(v) \leq \left(\frac{3}{2} \right)^{rank(A)}[/math], то: [math] 2^{rank(A)} \leq VAL(A) \leq |A| \left(\frac{3}{2} \right)^{rank(A)} \newline \newline |A| \geq \frac {2^{rank(A)}} {\left(\frac{3}{2} \right)^{rank(A)}} = \left( \frac {4} {3} \right)^{rank(A)} \newline \newline rank(A) \leq \log_{ \frac{4}{3} } { (|A|) } = O(\log {|A|}) = O(\log{n}) [/math] А так как [math]h(T_A) \leq rank(A)[/math], утверждение доказано.

[math]\triangleleft[/math]

Лемма (1):

Для всякого сокращенного дерева [math]T_A[/math] инвариант 3 выполняется

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

[math]\triangleright[/math]

Если [math]h(T_A) = 0[/math] (т. е. дерево состоит только из корня), то [math]VAL(A) = \left( \frac{3}{2} \right)^{0} = 1 [/math] и [math] 2^{rank(A)} = 2^0 = 1 \Rightarrow VAL(A) = 2^{rank(A)} [/math]. Если [math]h(T_A) = 1[/math], то [math]VAL(A) \geq \left( \frac{3}{2} \right)^{1} + \left( \frac{3}{2} \right)^{0} = \frac{5}{2} [/math] и [math]2^{rank(A)} = 2^1 = 2 \Rightarrow VAL(A) \geq 2^{rank(A)}[/math]

[math]\triangleleft[/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]VAL(C) \gt VAL(A) \geq 2^{rank(A)} = 2^{rank(C)}[/math]

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

[math]VAL(C) \gt VAL(A) + VAL(B) \geq 2^{rank(A)} + 2^{rank(B)} = 2^{1 + rank(A)} = 2^{rank(C)} [/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]y = p(x), g = p(y), k = rank(g) \Rightarrow rank(y) \leq k - 1[/math]. Следовательно, до переподвешивания [math]val(x) = \left( \frac{3}{2} \right)^{k - 1}[/math], а после переподвешивания [math]val(x) \leq \left( \frac{3}{2} \right)^{k}[/math]. Таким образом, при переподвешивании [math]x \; VAL(A)[/math] может только увеличиться. Тем временем [math]rank(A)[/math] остается неизменным, ведь [math]\mathrm{Relink}[/math] меняет ранг корня только тогда, когда дерево стало сокращенным, а сейчас мы рассматриваем только полные деревья. Из этого вытекает:
[math]VAL(A') \geq VAL(A) \geq 2^{rank(A)} = 2^{rank(A')}[/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]g = p(y), k = rank(g) \Rightarrow rank(y) \leq k - 1[/math]. Мы удаляем [math]x[/math] и отсоединяем 2 его братьев, их суммарное значение не больше [math]3 \left( \frac {3} {2} \right) ^ {k - 1} [/math]. Потом мы подвешиваем 2 братьев к [math]g[/math] — их суммарное значение становится [math]2 \left( \frac {3} {2} \right) ^ k [/math]. Итого, суммарное изменение значения не меньше
  [math]-3 \left( \frac {3} {2} \right) ^ {k - 1} + 2 \left( \frac {3} {2} \right) ^ k = 0[/math],
  

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

[math]VAL(A') \geq VAL(A)[/math]

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

[math]VAL(A') \geq VAL(A) \geq 2^{rank(A)} = 2^{rank(A')}[/math]

• Если Если [math]y = root[/math], то обозначим [math]k = rank(y) \Rightarrow rank(x) \leq k - 1[/math]. Обозначим некоторого брата [math]x[/math], не являющегося листом, как [math]c \Rightarrow rank(c) \leq k - 1[/math]. Мы удаляем [math]x[/math] и переподвешиваем 3 сыновей [math]c[/math], следовательно суммарное значение дерева сначала убывает на не более чем [math]\left( \frac {3} {2} \right) ^ k + 3 \left( \frac {3} {2} \right) ^ {k - 1}[/math] а после увеличивается на [math]3 \left( \frac {3} {2} \right) ^ k [/math]. Итого, суммарное изменение значения не меньше чем

[math] -\left( \frac {3} {2} \right) ^ k - 3 \left( \frac {3} {2} \right) ^ {k - 1} + 3 \left( \frac {3} {2} \right) ^ k[/math],

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

[math]VAL(A') \geq VAL(A)[/math],

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

[math]VAL(A') \geq VAL(A) \geq 2^{rank(A)} = 2^{rank(A')}[/math]

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

Выводы

Лемма:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Следствие 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] в среднем.

Ссылки

• A. Ben-Amram, S. Yoffe. A Simple And Efficient Union-Find-Delete Algorithm
• S. Alstrup, I. L. Gørtz, T. Rauhe, M. Thorup, and U. Zwick. Union-find with constant time deletions