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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ссылки)
м (rollbackEdits.php mass rollback)
 
(не показаны 84 промежуточные версии 5 участников)
Строка 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
 
|id=def_reduced_tree
|definition=Дерево, либо состоящее ровно из одной вершины, либо же из 1 вершины ранга 1 и листьев ранга 0, называется '''сокращенным''' (''reduced'')   
+
|definition=Дерево, либо состоящее ровно из одной вершины, либо же из <tex>1</tex> вершины ранга <tex>1</tex> и листьев ранга <tex>0</tex>, называется '''сокращенным''' (англ. ''reduced'').  
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|id=def_full_tree
 
|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 ===
 
=== Реализация операции 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 ===
 
=== Реализация операции 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>\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 ===
 
=== Реализация операции 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'>
 +
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
 +
\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-find with constant time deletions.]</ref>.
  
 
== Примечания ==
 
== Примечания ==
 
<references />
 
<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. Yoffe. A Simple And Efficient Union-Find-Delete Algorithm]
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
 
 +
[[Категория: Система непересекающихся множеств ]]

Текущая версия на 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]h(v) = \max \{ h(w) \: | \: w - \mathrm{ child \: of } \: v \} + 1[/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] его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.

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

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


Определение:
Дерево, либо состоящее ровно из одной вершины, либо же из [math]1[/math] вершины ранга [math]1[/math] и листьев ранга [math]0[/math], называется сокращенным (англ. reduced).


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


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

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

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

Тривиально:

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

Теперь рассмотрим случай, когда размеры обоих деревьев больше [math]4[/math]. Примем, не умаляя общности, что [math]rank(root(T_A)) \geqslant 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] на [math]1[/math].
  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][1], несмотря на то, что интуитивно кажется более медленным. Мы будем использовать именно разделение путей, потому что это серьезно упрощает поддержку списков и инвариантов.

Операция 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] осталось менее [math]3[/math] детей, проделаем шаги [math]1[/math] и [math]2[/math] и с ними тоже.
  4. Если после этого [math] p(x) [/math] стал листом, присвоим [math] rank(p(x)) = 0 [/math] и удалим [math] p(x) [/math] из [math]\mathrm{N_{LIST}}[/math] корня дерева.
  5. Если после этого [math]\mathrm{N_{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) \leqslant 4[/math] — удаление из такого дерева даст нам сокращенное дерево. Назовем эту процедуру [math]\mathrm{ReducedTreeDelete(a)} [/math].

Операция ReducedTreeDelete

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

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

Нам необходимо найти некоторый лист дерева, из которого мы удаляем элемент. Реализуем для этого процедуру [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]

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

  1. Если [math]p(x) \neq root(T)[/math], вызовем [math]\mathrm{Relink}[/math] для 2 самых правых детей [math]p(x)[/math]
  2. Иначе найдем среди детей [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]

  1. Если [math]size(T) \leqslant 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) \geqslant 2^{rank(A)} [/math]
Утверждение:
При выполнении инварианта 3 высота дерева не превышает [math]O(\log {n})[/math]
[math]\triangleright[/math]

Так как в [math]T_A[/math] есть [math]|A|[/math] вершин и [math]val(v) \leqslant \left(\frac{3}{2} \right)^{rank(A)}[/math], то:

[math] 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 \newline rank(A) \leqslant \log_{ \frac{4}{3} } { (|A|) } = O(\log {|A|}) = O(\log{n}) [/math]

А так как [math]h(T_A) \leqslant 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) \geqslant \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) \geqslant 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) \geqslant 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) \geqslant 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) \leqslant k - 1[/math]. Следовательно, до переподвешивания [math]val(x) = \left( \frac{3}{2} \right)^{k - 1}[/math], а после переподвешивания [math]val(x) \leqslant \left( \frac{3}{2} \right)^{k}[/math]. Таким образом, при переподвешивании [math]x \; VAL(A)[/math] может только увеличиться. Тем временем [math]rank(A)[/math] остается неизменным, ведь [math]\mathrm{Relink}[/math] меняет ранг корня только тогда, когда дерево стало сокращенным, а сейчас мы рассматриваем только полные деревья. Из этого вытекает:

[math]VAL(A') \geqslant VAL(A) \geqslant 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) \leqslant k - 1[/math]. Мы удаляем [math]x[/math] и отсоединяем [math]2[/math] его братьев, их суммарное значение не больше [math]3 \left( \frac {3} {2} \right) ^ {k - 1} [/math]. Потом мы подвешиваем [math]2[/math] братьев к [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') \geqslant VAL(A)[/math]

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

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


  • Если Если [math]y = root[/math], то обозначим [math]k = rank(y) \Rightarrow rank(x) \leqslant k - 1[/math]. Обозначим некоторого брата [math]x[/math], не являющегося листом, как [math]c \Rightarrow rank(c) \leqslant k - 1[/math]. Мы удаляем [math]x[/math] и переподвешиваем [math]3[/math] сыновей [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') \geqslant VAL(A)[/math],

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

[math]VAL(A') \geqslant VAL(A) \geqslant 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] в среднем[2].

Примечания

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