1632
правки
Изменения
м
Наша структура Структура данных должна поддерживать следующие операции:
rollbackEdits.php mass rollback
Реализация системы непересекающихся множеств с помощью [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|леса корневых деревьев]] не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за истинную <tex>O(1)</tex>, сохраняя асимптотику для операций <tex>\mathrm{ Union } </tex> и <tex>\mathrm{Find}</tex> и потребление памяти <tex>O(n)</tex>.
== Введение Описание ==
* <tex>\mathrm {Makeset(x)}</tex> {{---}} создать новое множество из <tex>1</tex> элемента <tex>x </tex>. Время: <tex>O(1)</tex>.
* <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>\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)</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> операции, не испортив при этом асимптотику всех остальных.
* '''вершиной дерева''' назовем объект, содержащий ссылки <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> его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.
Эти три нововведения необходимы для нахождения листа в дереве (как оказывается, это гораздо более нетривиальная задача).
{{Определение
|id=def_reduced_tree
|definition=Дерево, либо состоящее ровно из одной вершины, либо же из <tex>1</tex> вершины ранга <tex>1</tex> и листьев ранга <tex>0</tex>, называется '''сокращенным''' (англ. ''reduced'') .
}}
=== Реализация операции Makeset ===
Тривиально:
# Создадим узел <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>.
=== Реализация операции 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> пустым. (Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную)
=== Реализация операции 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> \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{NL_N_{LIST}}</tex> корня дерева.# Если после этого <tex>\mathrm{NL_N_{LIST}}</tex> корня стал пустым (это значит, что дерево стало сокращенным), присвоим <tex> rank(root) := 1 </tex>
Очевидно, что <tex>\mathrm{Relink} </tex> выполняется за <tex>O(1)</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>2</tex> шага обеспечивают сохранение полноты дерева
# Если <tex>p(x) \neq root(T)</tex>, вызовем <tex>\mathrm{Relink}</tex> для 2 самых правых детей <tex>p(x)</tex>
# Иначе найдем среди детей <tex>p(x)</tex> узел, не являющийся листом (с помощью <tex>\mathrm{NL_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} \; 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 ====
=== Delete ===
Пусть для множества <tex>A</tex> '''инвариант 3 ''' выполняется.
Если после выполнения <tex>\mathrm{Delete} \; T_A</tex> стало сокращенным, то '''инвариант 3''' сохранен по '''лемме 1'''.
<references />
== Источники информации ==
* [http://www2.mta.ac.il/~amirben/downloadable/ufd.pdf A. Ben-Amram, S. Yoffe. A Simple And Efficient Union-Find-Delete Algorithm]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Система непересекающихся множеств ]]
