СНМ с операцией удаления за О(1) — различия между версиями
(→Основные положения) |
м (rollbackEdits.php mass rollback) |
||
(не показана 51 промежуточная версия 5 участников) | |||
Строка 1: | Строка 1: | ||
Реализация системы непересекающихся множеств с помощью [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|леса корневых деревьев]] не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за истинную <tex>O(1)</tex>, сохраняя асимптотику для операций <tex>\mathrm{ Union } </tex> и <tex>\mathrm{Find}</tex> и потребление памяти <tex>O(n)</tex>. | Реализация системы непересекающихся множеств с помощью [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|леса корневых деревьев]] не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за истинную <tex>O(1)</tex>, сохраняя асимптотику для операций <tex>\mathrm{ Union } </tex> и <tex>\mathrm{Find}</tex> и потребление памяти <tex>O(n)</tex>. | ||
− | == | + | == Описание == |
− | + | Структура данных должна поддерживать следующие операции: | |
− | * <tex>\mathrm {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>\mathrm {Union(A, B)}</tex> {{---}} объединить множества A и B в одно. Время: <tex> O(1) </tex>, без учета времени на операцию <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>\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 из содержащего его множества. Время: 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>O(n) </tex> поддеревьев этой вершины. Однако, если вершина является листом, то ее можно удалять совершенно безболезненно. |
− | ;Соображение 1 : Пусть | + | |
− | ;Соображение 2 : Пусть | + | ;Соображение 1 : Пусть есть возможность менять произвольные вершины местами за <tex>O(1)</tex>. Тогда для удаления некоторой вершины достаточно поменять ее местами с каким-нибудь листом и удалить этот лист. |
− | + | ||
− | Все дальнейшие усилия направлены на то, чтобы поддержать эти 2 операции, не испортив при этом асимптотику всех остальных. | + | ;Соображение 2 : Пусть есть возможность находить какой-нибудь лист (неважно, какой именно) в дереве за <tex>O(1)</tex>. Тогда, по '''соображению 1''', мы уже умеем удалять произвольный элемент из дерева за <tex>O(1)</tex>. |
+ | |||
+ | Все дальнейшие усилия направлены на то, чтобы поддержать эти <tex>2</tex> операции, не испортив при этом асимптотику всех остальных. | ||
== Реализация == | == Реализация == | ||
=== Расширение структуры данных === | === Расширение структуры данных === | ||
Расширим [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|лес корневых деревьев]] следующим образом: | Расширим [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|лес корневых деревьев]] следующим образом: | ||
− | + | ==== Модификации для 1-го соображения ==== | |
− | + | Разделим понятия '''вершина дерева''' и '''элемент множества''': | |
− | + | * '''вершиной дерева''' назовем объект, содержащий ссылки <tex>next</tex>, <tex>prev</tex> и <tex>head</tex> (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине '''элемент множества'''; | |
− | + | * '''элемент множества''' {{---}} объект, содержащий значение элемента и ссылку на соотв. '''вершину дерева'''. | |
− | + | Это нововведение, очевидно, позволит менять элементы в дереве местами за <tex>O(1)</tex>. | |
− | + | ||
− | + | ==== Модификации для 2-го соображения ==== | |
− | + | * Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список <tex> \mathrm{C_{LIST}} </tex> ее детей. Будем считать, что дети упорядочены по направлению списка слева направо. | |
− | + | * Для корня каждого дерева храним двусвязный список <tex> \mathrm{N_{LIST}} </tex> его детей, не являющихся листьями. | |
− | + | * Для каждого дерева (включая поддеревья) храним циклический двусвязный список <tex> \mathrm{DFS_{LIST}} </tex> его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины. | |
+ | |||
+ | Эти три нововведения необходимы для нахождения листа в дереве (как оказывается, это гораздо более нетривиальная задача). | ||
+ | |||
Введем также следующие определения: | Введем также следующие определения: | ||
{{Определение | {{Определение | ||
|id=def_reduced_tree | |id=def_reduced_tree | ||
− | |definition=Дерево, либо состоящее ровно из одной вершины, либо же из 1 вершины ранга 1 и листьев ранга 0, называется '''сокращенным''' ('' | + | |definition=Дерево, либо состоящее ровно из одной вершины, либо же из <tex>1</tex> вершины ранга <tex>1</tex> и листьев ранга <tex>0</tex>, называется '''сокращенным''' (англ. ''reduced''). |
}} | }} | ||
{{Определение | {{Определение | ||
|id=def_full_tree | |id=def_full_tree | ||
− | |definition=Дерево называется '''полным''' ('' | + | |definition=Дерево называется '''полным''' (англ. ''full''), если каждый из его узлов либо является листом с рангом <tex>0</tex>, либо имеет не менее <tex>3</tex> детей. |
}} | }} | ||
В нашей структуре данных будет поддерживаться следующий инвариант: '''дерево всегда полное или сокращенное'''. | В нашей структуре данных будет поддерживаться следующий инвариант: '''дерево всегда полное или сокращенное'''. | ||
Этот инвариант влечет за собой очевидные следствия: | Этот инвариант влечет за собой очевидные следствия: | ||
− | * Все деревья (и поддеревья) размера < 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) | + | # Создадим узел <tex>v</tex> и свяжем его с элементом <tex>x</tex>. Установим: <tex>p(v) = v, rank(v) = 0</tex>. |
− | # Создадим для вершины <tex>v</tex> пустые списки <tex>\mathrm{ | + | # Создадим для вершины <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) | + | # <tex>\forall v \in T_B : \: p(v) = root(T_A), \: rank(v) = 0</tex>. |
− | # <tex> rank(root(T_A)) | + | # <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)) \ | + | Примем, не умаляя общности, что <tex>rank(root(T_A)) \geqslant rank(root(T_B))</tex>. Тогда: |
− | # <tex>p(root(T_B)) | + | # <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>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> пустым. (Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную) | ||
Строка 82: | Строка 87: | ||
=== Реализация операции Find === | === Реализация операции Find === | ||
− | В нашей реализации операции <tex>\mathrm {Find}</tex> вместо уже известного | + | В нашей реализации операции <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 ==== | ==== Операция Relink ==== | ||
Реализуем процедуру <tex> \mathrm { Relink(x) } </tex> {{---}} переподвешивание элемента <tex>x</tex> к его "дедушке" с сохранением инвариантов и структуры списков. | Реализуем процедуру <tex> \mathrm { Relink(x) } </tex> {{---}} переподвешивание элемента <tex>x</tex> к его "дедушке" с сохранением инвариантов и структуры списков. | ||
Строка 92: | Строка 97: | ||
#* Если <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>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> \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> осталось менее 3 детей, проделаем шаги 1 и 2 и с ними тоже. | + | # Если после этого у <tex>p(x)</tex> осталось менее <tex>3</tex> детей, проделаем шаги <tex>1</tex> и <tex>2</tex> и с ними тоже. |
− | # Если после этого <tex> p(x) </tex> стал листом, присвоим <tex> rank(p(x)) | + | # Если после этого <tex> p(x) </tex> стал листом, присвоим <tex> rank(p(x)) = 0 </tex> и удалим <tex> p(x) </tex> из <tex>\mathrm{N_{LIST}}</tex> корня дерева. |
− | # Если после этого <tex>\mathrm{ | + | # Если после этого <tex>\mathrm{N_{LIST}}</tex> корня стал пустым (это значит, что дерево стало сокращенным), присвоим <tex> rank(root) = 1 </tex> |
Очевидно, что <tex>\mathrm{Relink} </tex> выполняется за <tex>O(1)</tex> | Очевидно, что <tex>\mathrm{Relink} </tex> выполняется за <tex>O(1)</tex> | ||
Строка 102: | Строка 107: | ||
# Пусть <tex>x</tex> {{---}} вершина дерева, ассоциированная с элементом <tex>a</tex> | # Пусть <tex>x</tex> {{---}} вершина дерева, ассоциированная с элементом <tex>a</tex> | ||
# Пока <tex>p(x) \neq root</tex>, выполняем: | # Пока <tex>p(x) \neq root</tex>, выполняем: | ||
− | ## <tex>t | + | ## <tex>t = p(x)</tex> |
## <tex>Relink(x)</tex> | ## <tex>Relink(x)</tex> | ||
− | ## <tex>x | + | ## <tex>x = t</tex> |
=== Реализация операции Delete === | === Реализация операции Delete === | ||
− | Сначала разработаем процедуру удаления узла из дерева, у которого <tex>size(T) \ | + | Сначала разработаем процедуру удаления узла из дерева, у которого <tex>size(T) \leqslant 4</tex> {{---}} удаление из такого дерева даст нам сокращенное дерево. Назовем эту процедуру <tex>\mathrm{ReducedTreeDelete(a)} </tex>. |
==== Операция ReducedTreeDelete ==== | ==== Операция ReducedTreeDelete ==== | ||
− | # Если дерево не сокращенное, сделаем его сокращенным, просто переподвесив все вершины к корню. Так как дерево маленькое {{---}} <tex>size(T) \ | + | # Если дерево не сокращенное, сделаем его сокращенным, просто переподвесив все вершины к корню. Так как дерево маленькое {{---}} <tex>size(T) \leqslant 4</tex> {{---}} операция выполняется за <tex>O(1)</tex> |
# Если <tex>a</tex> ассоциирован с листом, просто удалим этот лист. | # Если <tex>a</tex> ассоциирован с листом, просто удалим этот лист. | ||
# Иначе <tex>a</tex> ассоциирован с корнем: просто поменяем <tex>a</tex> местами с элементом из любого листа (любого сына корня) и удалим этот лист. | # Иначе <tex>a</tex> ассоциирован с корнем: просто поменяем <tex>a</tex> местами с элементом из любого листа (любого сына корня) и удалим этот лист. | ||
− | Теперь подумаем, как удалять элемент из полного дереве размера больше 4. После удаления дерево должно остаться полным. | + | Теперь подумаем, как удалять элемент из полного дереве размера больше <tex>4</tex>. После удаления дерево должно остаться полным. |
+ | |||
Нам необходимо найти некоторый лист дерева, из которого мы удаляем элемент. Реализуем для этого процедуру <tex>\mathrm{FindLeaf(a)}</tex>. | Нам необходимо найти некоторый лист дерева, из которого мы удаляем элемент. Реализуем для этого процедуру <tex>\mathrm{FindLeaf(a)}</tex>. | ||
==== Операция FindLeaf ==== | ==== Операция FindLeaf ==== | ||
Строка 128: | Строка 134: | ||
# Извлекаем <tex>x</tex> из <tex>\mathrm{C_{LIST}} \; p(x) </tex> и из <tex>\mathrm{DFS_{LIST}}</tex> | # Извлекаем <tex>x</tex> из <tex>\mathrm{C_{LIST}} \; p(x) </tex> и из <tex>\mathrm{DFS_{LIST}}</tex> | ||
# Удаляем узел <tex>x</tex> | # Удаляем узел <tex>x</tex> | ||
− | Следующие 2 шага обеспечивают сохранение полноты дерева | + | Следующие <tex>2</tex> шага обеспечивают сохранение полноты дерева |
# Если <tex>p(x) \neq root(T)</tex>, вызовем <tex>\mathrm{Relink}</tex> для 2 самых правых детей <tex>p(x)</tex> | # Если <tex>p(x) \neq root(T)</tex>, вызовем <tex>\mathrm{Relink}</tex> для 2 самых правых детей <tex>p(x)</tex> | ||
− | # Иначе найдем среди детей <tex>p(x)</tex> узел, не являющийся листом (с помощью <tex>\mathrm{ | + | # Иначе найдем среди детей <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{Relink}</tex> сохраняет полноту дерева и выполняется за <tex>O(1)</tex>, <tex>\mathrm{DeleteLeaf}</tex>, очевидно, обладает теми же свойствами. | ||
− | + | ||
Итак, соберем воедино операцию <tex>\mathrm{Delete(a)}</tex>: | Итак, соберем воедино операцию <tex>\mathrm{Delete(a)}</tex>: | ||
+ | |||
==== Операция Delete ==== | ==== Операция Delete ==== | ||
Пусть элемент <tex>a</tex> ассоциирован с вершиной <tex>x</tex> | Пусть элемент <tex>a</tex> ассоциирован с вершиной <tex>x</tex> | ||
− | # Если <tex>size(T) \ | + | # Если <tex>size(T) \leqslant 4</tex>, вызываем <tex>\mathrm{ReducedTreeDelete(a)}</tex> |
# Иначе: | # Иначе: | ||
− | ## <tex>l | + | ## <tex>l = \mathrm{FindLeaf(a)} </tex> |
## Поменяем элементы в <tex>x</tex> и <tex>l</tex> местами. | ## Поменяем элементы в <tex>x</tex> и <tex>l</tex> местами. | ||
## <tex>\mathrm{DeleteLeaf(l)}</tex> | ## <tex>\mathrm{DeleteLeaf(l)}</tex> | ||
Строка 148: | Строка 155: | ||
{{Определение | {{Определение | ||
|id=def_value_node | |id=def_value_node | ||
− | |definition=Определим '''значение''' вершины <tex>v</tex> {{---}} <tex>val(v)</tex> {{---}} следующим образом: | + | |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 | |id=def_value_tree | ||
− | |definition='''Значение множества''' <tex>A</tex> {{---}} <tex>VAL(A)</tex> {{---}} сумма значений вершин <tex>T_A</tex>: | + | |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> {{---}} поддерживают следующий инвариант: | Нам необходимо доказать, что все определенные нами операции {{---}} <tex>\mathrm{Makeset}</tex>, <tex>\mathrm{Union}</tex>, <tex>\mathrm{Find}</tex> и <tex>\mathrm{Delete}</tex> {{---}} поддерживают следующий инвариант: | ||
; Инвариант 3: | ; Инвариант 3: | ||
− | : <tex>VAL(A) \ | + | : <tex>VAL(A) \geqslant 2^{rank(A)} </tex> |
{{Утверждение | {{Утверждение | ||
|statement= | |statement= | ||
− | При выполнении инварианта 3 высота дерева не превышает <tex>O(\log {n})</tex> | + | При выполнении '''инварианта 3''' высота дерева не превышает <tex>O(\log {n})</tex> |
|proof= | |proof= | ||
− | Так как в <tex>T_A</tex> есть <tex>|A|</tex> вершин и <tex>val(v) \ | + | Так как в <tex>T_A</tex> есть <tex>|A|</tex> вершин и <tex dpi='140'>val(v) \leqslant \left(\frac{3}{2} \right)^{rank(A)}</tex>, то: |
+ | |||
<center> | <center> | ||
− | <tex> | + | <tex dpi='160'> |
− | 2^{rank(A)} \ | + | 2^{rank(A)} \leqslant VAL(A) \leqslant |A| \left(\frac{3}{2} \right)^{rank(A)} |
\newline | \newline | ||
\newline | \newline | ||
− | |A| \ | + | |A| \geqslant \frac {2^{rank(A)}} {\left(\frac{3}{2} \right)^{rank(A)}} = \left( \frac {4} {3} \right)^{rank(A)} |
\newline | \newline | ||
\newline | \newline | ||
− | rank(A) \ | + | rank(A) \leqslant \log_{ \frac{4}{3} } { (|A|) } = O(\log {|A|}) = O(\log{n}) |
</tex> | </tex> | ||
</center> | </center> | ||
− | А так как <tex>h(T_A) \ | + | А так как <tex>h(T_A) \leqslant rank(A)</tex>, утверждение доказано. |
}} | }} | ||
Строка 182: | Строка 196: | ||
|author=1 | |author=1 | ||
|statement= | |statement= | ||
− | Для всякого сокращенного дерева <tex>T_A</tex> инвариант 3 выполняется | + | Для всякого сокращенного дерева <tex>T_A</tex> '''инвариант 3''' выполняется |
|proof= | |proof= | ||
− | Если <tex>h(T_A) = 0</tex> (т. е. дерево состоит только из корня), то <tex>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) = 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>VAL(A) \ | + | |
+ | Если <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. | + | Докажем теперь, что каждая из операций сохраняет '''инвариант 3'''. |
=== Makeset === | === Makeset === | ||
− | Т. к. операция <tex>\mathrm{Makeset}</tex> создает сокращенное дерево, то по лемме 1 <tex>\mathrm{Makeset}</tex> сохраняет инвариант 3 | + | Т. к. операция <tex>\mathrm{Makeset}</tex> создает сокращенное дерево, то по '''лемме 1''' <tex>\mathrm{Makeset}</tex> сохраняет '''инвариант 3''' |
=== Union === | === Union === | ||
− | Пусть для множеств <tex>A</tex> и <tex>B</tex> инвариант 3 выполняется. | + | Пусть для множеств <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>, и следовательно, | + | |
+ | Пусть <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> и имеем: | Пусть теперь <tex>rank(A) = rank(B)</tex>, тогда <tex>rank(C) = rank(A) + 1</tex> и имеем: | ||
− | + | ||
− | Следовательно, операция <tex>\mathrm{Union}</tex> сохраняет инвариант 3. | + | <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 === | === Find === | ||
− | Пусть для множества <tex>A</tex> инвариант 3 выполняется. | + | Пусть для множества <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{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 ==== | ==== Анализ операции Relink ==== | ||
− | Операция <tex>\mathrm{Relink}</tex> переподвешивает узел <tex>x</tex> к <tex>p(p(x))</tex>. | + | Операция <tex>\mathrm{Relink}</tex> переподвешивает узел <tex>x</tex> к <tex>p(p(x))</tex>. |
− | Итак, операция <tex>\mathrm{Relink}</tex> сохраняет инвариант 3, следовательно {{---}} операция <tex>\mathrm{Find}</tex> сохраняет инвариант 3. | + | |
+ | Пусть <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 === | === Delete === | ||
− | Пусть для множества <tex>A</tex> инвариант 3 выполняется. | + | Пусть для множества <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{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>. | Так как операция <tex>\mathrm{FindLeaf}</tex> и обмен элементами между узлами не меняют структуры дерева, достаточно рассмотреть операцию <tex>\mathrm{DeleteLeaf}</tex>. | ||
==== Анализ операции DeleteLeaf ==== | ==== Анализ операции DeleteLeaf ==== | ||
Пусть <tex>x</tex> {{---}} удаляемый элемент, <tex>y = p(x)</tex>. | Пусть <tex>x</tex> {{---}} удаляемый элемент, <tex>y = p(x)</tex>. | ||
− | * Если <tex>y \neq root</tex>, то обозначим <tex>g = p(y), k = rank(g) \Rightarrow rank(y) \ | + | * Если <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') \ | + | <center><tex>VAL(A') \geqslant VAL(A)</tex></center> |
+ | |||
<tex>\mathrm{Delete} </tex> меняет <tex> rank(A) </tex> только когда дерево становится сокращенным, а мы рассматриваем только полные, следовательно {{---}} <tex> rank(A) </tex> не меняется, следовательно: | <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) \ | + | * Если Если <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> -\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 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') \ | + | <center><tex>VAL(A') \geqslant VAL(A)</tex>,</center> |
а так как <tex>2^{rank(A)} = 2^{rank(A')}</tex>, то | а так как <tex>2^{rank(A)} = 2^{rank(A')}</tex>, то | ||
− | <center><tex>VAL(A') \ | + | <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> сохраняет его. | + | Итак, операция <tex>\mathrm{DeleteLeaf}</tex> сохраняет '''инвариант 3''', а значит, и операция <tex>\mathrm{Delete} </tex> сохраняет его. |
=== Выводы === | === Выводы === | ||
Строка 237: | Строка 277: | ||
|id=lemma_2 | |id=lemma_2 | ||
|statement= | |statement= | ||
− | В вышеописанной структуре данных инвариант 3 сохраняется до и после каждой операции | + | В вышеописанной структуре данных '''инвариант 3''' сохраняется до и после каждой операции |
|proof= | |proof= | ||
− | Изначально дерево является сокращенным и инвариант 3 выполняется в нем по лемме 1; каждая последующая операция сохраняет инвариант {{---}} лемма доказана. | + | Изначально дерево является сокращенным и '''инвариант 3''' выполняется в нем по '''лемме 1'''; каждая последующая операция сохраняет инвариант {{---}} лемма доказана. |
}} | }} | ||
; Следствие 1 | ; Следствие 1 | ||
: Высота дерева никогда не превышает <tex>O(\log {n})</tex>, следовательно операция <tex>\mathrm{Find}</tex> занимает <tex>O(\log {n})</tex> в худшем случае. | : Высота дерева никогда не превышает <tex>O(\log {n})</tex>, следовательно операция <tex>\mathrm{Find}</tex> занимает <tex>O(\log {n})</tex> в худшем случае. | ||
; Следствие 2 | ; Следствие 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 | + | : <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. Ben-Amram, S. Yoffe. 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
Реализация системы непересекающихся множеств с помощью леса корневых деревьев не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за истинную , сохраняя асимптотику для операций и и потребление памяти .
Описание
Структура данных должна поддерживать следующие операции:
- — создать новое множество из элемента . Время: .
- — объединить множества и в одно. Время: , без учета времени на операцию , которая используется, если множества и заданы своими произвольными представителями.
- — найти множество, в котором содержится элемент . Время: в худшем случае, — в среднем ( — обратная функция Аккермана), где — размер множества.
- — удалить элемент x из содержащего его множества. Время: .
В дальнейшем используются следующие понятия и обозначения:
- — размер множества (количество элементов в нем).
- — корень дерева .
- — высота вершины : если является листом, то , иначе .
- — родитель вершины . Если — корень, то считаем, что .
- — ранг вершины, некоторая верхняя оценка на ее высоту.
Как и в реализации с помощью леса корневых деревьев, выполнено следующее: .
Идея
В реализации СНМ с помощью леса корневых деревьев нет возможности удалить произвольную вершину из множества за разумное время — в таком случае придется переподвешивать
поддеревьев этой вершины. Однако, если вершина является листом, то ее можно удалять совершенно безболезненно.- Соображение 1
- Пусть есть возможность менять произвольные вершины местами за . Тогда для удаления некоторой вершины достаточно поменять ее местами с каким-нибудь листом и удалить этот лист.
- Соображение 2
- Пусть есть возможность находить какой-нибудь лист (неважно, какой именно) в дереве за . Тогда, по соображению 1, мы уже умеем удалять произвольный элемент из дерева за .
Все дальнейшие усилия направлены на то, чтобы поддержать эти
операции, не испортив при этом асимптотику всех остальных.Реализация
Расширение структуры данных
Расширим лес корневых деревьев следующим образом:
Модификации для 1-го соображения
Разделим понятия вершина дерева и элемент множества:
- вершиной дерева назовем объект, содержащий ссылки , и (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине элемент множества;
- элемент множества — объект, содержащий значение элемента и ссылку на соотв. вершину дерева.
Это нововведение, очевидно, позволит менять элементы в дереве местами за
.Модификации для 2-го соображения
- Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список ее детей. Будем считать, что дети упорядочены по направлению списка слева направо.
- Для корня каждого дерева храним двусвязный список его детей, не являющихся листьями.
- Для каждого дерева (включая поддеревья) храним циклический двусвязный список его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.
Эти три нововведения необходимы для нахождения листа в дереве (как оказывается, это гораздо более нетривиальная задача).
Введем также следующие определения:
Определение: |
Дерево, либо состоящее ровно из одной вершины, либо же из | вершины ранга и листьев ранга , называется сокращенным (англ. reduced).
Определение: |
Дерево называется полным (англ. full), если каждый из его узлов либо является листом с рангом | , либо имеет не менее детей.
В нашей структуре данных будет поддерживаться следующий инвариант: дерево всегда полное или сокращенное.
Этот инвариант влечет за собой очевидные следствия:
- Все деревья (и поддеревья) размера — сокращенные, а — полные
- Каждая вершина, среди детей которой есть хотя бы нелистовая вершина, имеет не менее детей (это не позволяет дереву вытягиваться в бамбук, например)
Реализация операции Makeset
Тривиально:
- Создадим узел и свяжем его с элементом . Установим: .
- Создадим для вершины пустые списки и .
- Создадим с одним элементом — вершина .
Очевидно, что операция соблюдает инварианты и выполняется за
.Реализация операции Union
Пусть
— деревья, реализующие множества и соответственно. Пусть размер одного из деревьев меньше ; не умаляя общности — . Тогда действуем следующим образом:- .
- .
- Присоединим и для в конец и для .
Теперь рассмотрим случай, когда размеры обоих деревьев больше
. Примем, не умаляя общности, что . Тогда:- , и если , увеличим на .
- Вставим в начало и для .
- Вставим для в для сразу после .
- Сделаем для пустым. (Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную)
Если в качестве идентификаторов множеств нам переданы произвольные представители этих множеств, нам придется запустить процедуру
для каждого из них, чтобы найти корни деревьев. Без учета вызова процедуры мы сделаем операций.Реализация операции Find
В нашей реализации операции [1], несмотря на то, что интуитивно кажется более медленным. Мы будем использовать именно разделение путей, потому что это серьезно упрощает поддержку списков и инвариантов.
вместо уже известного метода сжатия путей (англ. path compressing) будем использовать разделение путей (англ. path splitting). Он заключается в том, чтобы при выполнении операции перевешивать элемент, от которого мы вызвались, не сразу к корню, а к собственному "дедушке". Такой метод сокращения пути приводит к той же амотризационной оценке для функцииОперация Relink
Реализуем процедуру
— переподвешивание элемента к его "дедушке" с сохранением инвариантов и структуры списков.- Удалим
- Если имеет брата справа от себя, вставим его в сразу слева от
- Иначе (если — крайний правый сын ) — вставим сразу справа от
из и вставим его в следующим образом:
- Обновим
- Если — крайний правый сын , то на предыдущем шаге мы вставили его в список детей сразу после , следовательно — порядок обхода вершин из в глубину не изменился. Значит, нам не нужно менять .
- В противном случае нам нужно поместить участок , соответствующий поддереву , перед . Этот участок — полуинтервал , где — сосед справа. Вырежем его и вставим перед .
следующим образом:
- Если после этого у осталось менее детей, проделаем шаги и и с ними тоже.
- Если после этого стал листом, присвоим и удалим из корня дерева.
- Если после этого корня стал пустым (это значит, что дерево стало сокращенным), присвоим
Очевидно, что
выполняется заОперация Find
Реализуем собственно операцию
:- Пусть — вершина дерева, ассоциированная с элементом
- Пока
Реализация операции Delete
Сначала разработаем процедуру удаления узла из дерева, у которого
— удаление из такого дерева даст нам сокращенное дерево. Назовем эту процедуру .Операция ReducedTreeDelete
- Если дерево не сокращенное, сделаем его сокращенным, просто переподвесив все вершины к корню. Так как дерево маленькое — — операция выполняется за
- Если ассоциирован с листом, просто удалим этот лист.
- Иначе ассоциирован с корнем: просто поменяем местами с элементом из любого листа (любого сына корня) и удалим этот лист.
Теперь подумаем, как удалять элемент из полного дереве размера больше
. После удаления дерево должно остаться полным.Нам необходимо найти некоторый лист дерева, из которого мы удаляем элемент. Реализуем для этого процедуру
.Операция FindLeaf
- Пусть элемент ассоциирован с вершиной .
- Если — лист, задача решена.
- Если — корень дерева, то он является первым в . Но при обходе в глубину последняя пройденная вершина всегда является листом, а значит — вершина, идущая в перед корнем, является листом. Возвращаем ее.
- В противном случае:
- Если имеет брата справа — , то перед тем как обойти поиском в глубину, мы обошли самый правый лист поддерева . Следовательно, нужный нам лист — .
- Иначе имеет брата слева — , и по аналогичным рассуждениям листом является .
Итак, мы нашли некоторый лист дерева за
. Теперь нам нужно просто уметь его удалять, но так, чтобы инварианты и структура списков сохранялись.Операция DeleteLeaf
Пусть
— удаляемый лист.- Извлекаем из и из
- Удаляем узел
Следующие
шага обеспечивают сохранение полноты дерева- Если , вызовем для 2 самых правых детей
- Иначе найдем среди детей узел, не являющийся листом (с помощью ), и вызовем для его самых правых детей.
Так как операция
сохраняет полноту дерева и выполняется за , , очевидно, обладает теми же свойствами.Итак, соберем воедино операцию
:Операция Delete
Пусть элемент
ассоциирован с вершиной- Если , вызываем
- Иначе:
- Поменяем элементы в и местами.
Анализ
Основные положения
Докажем верхнюю оценку стоимости операции
в .Определение: |
Определим значение вершины
| — — следующим образом:
Определение: |
Значение множества
| — — сумма значений вершин :
Нам необходимо доказать, что все определенные нами операции — , , и — поддерживают следующий инвариант:
- Инвариант 3
Утверждение: |
При выполнении инварианта 3 высота дерева не превышает |
Так как в есть вершин и , то:
|
Лемма (1): |
Для всякого сокращенного дерева инвариант 3 выполняется |
Доказательство: |
Если Если (т. е. дерево состоит только из корня), то и . , то и |
Докажем теперь, что каждая из операций сохраняет инвариант 3.
Makeset
Т. к. операция
создает сокращенное дерево, то по лемме 1 сохраняет инвариант 3Union
Пусть для множеств
и инвариант 3 выполняется.Пусть
. Пусть, не умаляя общности, . Тогда мы подвесим к корню , и будет равным , и следовательно,
Пусть теперь
, тогда и имеем:Следовательно, операция
сохраняет инвариант 3.Find
Пусть для множества
инвариант 3 выполняется.Операция
изменяет дерево . Если после выполнения стало сокращенным, то инвариант 3 сохранен по лемме 1.Осталось рассмотреть другой случай — когда до и после выполнения
было полным. Обозначим множество после выполнения какТак как
изменяет только посредством операции , достаточно доказать, что сохраняет инвариант 3.Анализ операции Relink
Операция
переподвешивает узел к .Пусть
. Следовательно, до переподвешивания , а после переподвешивания . Таким образом, при переподвешивании может только увеличиться. Тем временем остается неизменным, ведь меняет ранг корня только тогда, когда дерево стало сокращенным, а сейчас мы рассматриваем только полные деревья. Из этого вытекает:Итак, операция
сохраняет инвариант 3, следовательно — операция сохраняет инвариант 3.Delete
Пусть для множества
инвариант 3 выполняется.Если после выполнения
стало сокращенным, то инвариант 3 сохранен по лемме 1.Осталось рассмотреть случай, когда до и после выполнения
было полным. Обозначим множество после выполнения какТак как операция
и обмен элементами между узлами не меняют структуры дерева, достаточно рассмотреть операцию .Анализ операции DeleteLeaf
Пусть
— удаляемый элемент, .- Если , то обозначим . Мы удаляем и отсоединяем его братьев, их суммарное значение не больше . Потом мы подвешиваем братьев к — их суммарное значение становится . Итого, суммарное изменение значения не меньше
следовательно,
меняет только когда дерево становится сокращенным, а мы рассматриваем только полные, следовательно — не меняется, следовательно:
- Если Если , то обозначим . Обозначим некоторого брата , не являющегося листом, как . Мы удаляем и переподвешиваем сыновей , следовательно суммарное значение дерева сначала убывает на не более чем а после увеличивается на . Итого, суммарное изменение значения не меньше чем
следовательно
а так как
, то
Итак, операция сохраняет инвариант 3, а значит, и операция сохраняет его.
Выводы
Лемма: |
В вышеописанной структуре данных инвариант 3 сохраняется до и после каждой операции |
Доказательство: |
Изначально дерево является сокращенным и инвариант 3 выполняется в нем по лемме 1; каждая последующая операция сохраняет инвариант — лемма доказана. |
- Следствие 1
- Высота дерева никогда не превышает , следовательно операция занимает в худшем случае.
- Следствие 2
- [2]. занимает в среднем