СНМ с операцией удаления за О(1) — различия между версиями
(→Описание) |
(→Идея) |
||
Строка 25: | Строка 25: | ||
;Соображение 1 : Пусть мы умеем менять произвольные вершины местами за <tex>O(1)</tex>. Тогда для удаления некоторой вершины достаточно поменять ее местами с каким-нибудь листом и удалить этот лист. | ;Соображение 1 : Пусть мы умеем менять произвольные вершины местами за <tex>O(1)</tex>. Тогда для удаления некоторой вершины достаточно поменять ее местами с каким-нибудь листом и удалить этот лист. | ||
− | ;Соображение 2 : Пусть мы умеем находить какой-нибудь лист (неважно, какой именно) в дереве за <tex>O(1)</tex>. Тогда, по '''соображению 1''', мы уже умеем удалять произвольный элемент из дерева за <tex>O(1)</tex> | + | ;Соображение 2 : Пусть мы умеем находить какой-нибудь лист (неважно, какой именно) в дереве за <tex>O(1)</tex>. Тогда, по '''соображению 1''', мы уже умеем удалять произвольный элемент из дерева за <tex>O(1)</tex>. |
Все дальнейшие усилия направлены на то, чтобы поддержать эти <tex>2</tex> операции, не испортив при этом асимптотику всех остальных. | Все дальнейшие усилия направлены на то, чтобы поддержать эти <tex>2</tex> операции, не испортив при этом асимптотику всех остальных. |
Версия 19:31, 1 июня 2015
Реализация системы непересекающихся множеств с помощью леса корневых деревьев не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за истинную , сохраняя асимптотику для операций и и потребление памяти .
Содержание
Описание
Структура данных должна поддерживать следующие операции:
- — создать новое множество из элемента . Время: .
- — объединить множества и в одно. Время: , без учета времени на операцию , которая используется, если множества и заданы своими произвольными представителями.
- — найти множество, в котором содержится элемент . Время: в худшем случае, — в среднем ( — обратная функция Аккермана), где — размер множества.
- — удалить элемент 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]. занимает в среднем