СНМ с операцией удаления за О(1)
Реализация системы непересекающихся множеств с помощью леса корневых деревьев не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за истинную , сохраняя асимптотику для операций и и потребление памяти .
Описание
Структура данных должна поддерживать следующие операции:
- — создать новое множество из элемента . Время: .
- — объединить множества и в одно. Время: , без учета времени на операцию , которая используется, если множества и заданы своими произвольными представителями.
- — найти множество, в котором содержится элемент . Время: в худшем случае, — в среднем ( — обратная функция Аккермана), где — размер множества.
- — удалить элемент x из содержащего его множества. Время: .
В дальнейшем используются следующие понятия и обозначения:
- — размер множества (количество элементов в нем).
- — корень дерева .
- — высота вершины : если является листом, то , иначе .
- — родитель вершины . Если — корень, то считаем, что .
- — ранг вершины, некоторая верхняя оценка на ее высоту.
Как и в реализации с помощью леса корневых деревьев, выполнено следующее: .
Идея
В реализации СНМ с помощью леса корневых деревьев нет возможности удалить произвольную вершину из множества за разумное время — в таком случае придется переподвешивать поддеревьев этой вершины. Однако, если вершина является листом, то ее можно удалять совершенно безболезненно.
- Соображение 1
- Пусть есть возможность менять произвольные вершины местами за . Тогда для удаления некоторой вершины достаточно поменять ее местами с каким-нибудь листом и удалить этот лист.
- Соображение 2
- Пусть есть возможность находить какой-нибудь лист (неважно, какой именно) в дереве за . Тогда, по соображению 1, мы уже умеем удалять произвольный элемент из дерева за .
Все дальнейшие усилия направлены на то, чтобы поддержать эти операции, не испортив при этом асимптотику всех остальных.
Реализация
Расширение структуры данных
Расширим лес корневых деревьев следующим образом:
Модификации для 1-го соображения
Разделим понятия вершина дерева и элемент множества:
- вершиной дерева назовем объект, содержащий ссылки , и (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине элемент множества;
- элемент множества — объект, содержащий значение элемента и ссылку на соотв. вершину дерева.
Это нововведение, очевидно, позволит менять элементы в дереве местами за .
Модификации для 2-го соображения
- Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список ее детей. Будем считать, что дети упорядочены по направлению списка слева направо.
- Для корня каждого дерева храним двусвязный список его детей, не являющихся листьями.
- Для каждого дерева (включая поддеревья) храним циклический двусвязный список его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.
Эти три нововведения необходимы для нахождения листа в дереве (как оказывается, это гораздо более нетривиальная задача).
Введем также следующие определения:
| Определение: |
| Дерево, либо состоящее ровно из одной вершины, либо же из вершины ранга и листьев ранга , называется сокращенным (англ. reduced). |
| Определение: |
| Дерево называется полным (англ. full), если каждый из его узлов либо является листом с рангом , либо имеет не менее детей. |
В нашей структуре данных будет поддерживаться следующий инвариант: дерево всегда полное или сокращенное.
Этот инвариант влечет за собой очевидные следствия:
- Все деревья (и поддеревья) размера — сокращенные, а — полные
- Каждая вершина, среди детей которой есть хотя бы нелистовая вершина, имеет не менее детей (это не позволяет дереву вытягиваться в бамбук, например)
Реализация операции Makeset
Тривиально:
- Создадим узел и свяжем его с элементом . Установим: .
- Создадим для вершины пустые списки и .
- Создадим с одним элементом — вершина .
Очевидно, что операция соблюдает инварианты и выполняется за .
Реализация операции Union
Пусть — деревья, реализующие множества и соответственно. Пусть размер одного из деревьев меньше ; не умаляя общности — . Тогда действуем следующим образом:
- .
- .
- Присоединим и для в конец и для .
Теперь рассмотрим случай, когда размеры обоих деревьев больше . Примем, не умаляя общности, что . Тогда:
- , и если , увеличим на .
- Вставим в начало и для .
- Вставим для в для сразу после .
- Сделаем для пустым. (Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную)
Если в качестве идентификаторов множеств нам переданы произвольные представители этих множеств, нам придется запустить процедуру для каждого из них, чтобы найти корни деревьев. Без учета вызова процедуры мы сделаем операций.
Реализация операции Find
В нашей реализации операции вместо уже известного метода сжатия путей (англ. path compressing) будем использовать разделение путей (англ. path splitting). Он заключается в том, чтобы при выполнении операции перевешивать элемент, от которого мы вызвались, не сразу к корню, а к собственному "дедушке". Такой метод сокращения пути приводит к той же амотризационной оценке для функции [1], несмотря на то, что интуитивно кажется более медленным. Мы будем использовать именно разделение путей, потому что это серьезно упрощает поддержку списков и инвариантов.
Операция Relink
Реализуем процедуру — переподвешивание элемента к его "дедушке" с сохранением инвариантов и структуры списков.
- Удалим из и вставим его в следующим образом:
- Если имеет брата справа от себя, вставим его в сразу слева от
- Иначе (если — крайний правый сын ) — вставим сразу справа от
- Обновим следующим образом:
- Если — крайний правый сын , то на предыдущем шаге мы вставили его в список детей сразу после , следовательно — порядок обхода вершин из в глубину не изменился. Значит, нам не нужно менять .
- В противном случае нам нужно поместить участок , соответствующий поддереву , перед . Этот участок — полуинтервал , где — сосед справа. Вырежем его и вставим перед .
- Если после этого у осталось менее детей, проделаем шаги и и с ними тоже.
- Если после этого стал листом, присвоим и удалим из корня дерева.
- Если после этого корня стал пустым (это значит, что дерево стало сокращенным), присвоим
Очевидно, что выполняется за
Операция Find
Реализуем собственно операцию :
- Пусть — вершина дерева, ассоциированная с элементом
- Пока , выполняем:
Реализация операции Delete
Сначала разработаем процедуру удаления узла из дерева, у которого — удаление из такого дерева даст нам сокращенное дерево. Назовем эту процедуру .
Операция ReducedTreeDelete
- Если дерево не сокращенное, сделаем его сокращенным, просто переподвесив все вершины к корню. Так как дерево маленькое — — операция выполняется за
- Если ассоциирован с листом, просто удалим этот лист.
- Иначе ассоциирован с корнем: просто поменяем местами с элементом из любого листа (любого сына корня) и удалим этот лист.
Теперь подумаем, как удалять элемент из полного дереве размера больше . После удаления дерево должно остаться полным.
Нам необходимо найти некоторый лист дерева, из которого мы удаляем элемент. Реализуем для этого процедуру .
Операция FindLeaf
- Пусть элемент ассоциирован с вершиной .
- Если — лист, задача решена.
- Если — корень дерева, то он является первым в . Но при обходе в глубину последняя пройденная вершина всегда является листом, а значит — вершина, идущая в перед корнем, является листом. Возвращаем ее.
- В противном случае:
- Если имеет брата справа — , то перед тем как обойти поиском в глубину, мы обошли самый правый лист поддерева . Следовательно, нужный нам лист — .
- Иначе имеет брата слева — , и по аналогичным рассуждениям листом является .
Итак, мы нашли некоторый лист дерева за . Теперь нам нужно просто уметь его удалять, но так, чтобы инварианты и структура списков сохранялись.
Операция DeleteLeaf
Пусть — удаляемый лист.
- Извлекаем из и из
- Удаляем узел
Следующие шага обеспечивают сохранение полноты дерева
- Если , вызовем для 2 самых правых детей
- Иначе найдем среди детей узел, не являющийся листом (с помощью ), и вызовем для его самых правых детей.
Так как операция сохраняет полноту дерева и выполняется за , , очевидно, обладает теми же свойствами.
Итак, соберем воедино операцию :
Операция Delete
Пусть элемент ассоциирован с вершиной
- Если , вызываем
- Иначе:
- Поменяем элементы в и местами.
Анализ
Основные положения
Докажем верхнюю оценку стоимости операции в .
| Определение: |
| Определим значение вершины — — следующим образом:
|
| Определение: |
| Значение множества — — сумма значений вершин :
|
Нам необходимо доказать, что все определенные нами операции — , , и — поддерживают следующий инвариант:
- Инвариант 3
| Утверждение: |
При выполнении инварианта 3 высота дерева не превышает |
|
Так как в есть вершин и , то:
|
| Лемма (1): |
Для всякого сокращенного дерева инвариант 3 выполняется |
| Доказательство: |
|
Если (т. е. дерево состоит только из корня), то и . Если , то и |
Докажем теперь, что каждая из операций сохраняет инвариант 3.
Makeset
Т. к. операция создает сокращенное дерево, то по лемме 1 сохраняет инвариант 3
Union
Пусть для множеств и инвариант 3 выполняется.
Пусть . Пусть, не умаляя общности, . Тогда мы подвесим к корню , и будет равным , и следовательно,
Пусть теперь , тогда и имеем:
Следовательно, операция сохраняет инвариант 3.
Find
Пусть для множества инвариант 3 выполняется.
Операция изменяет дерево . Если после выполнения стало сокращенным, то инвариант 3 сохранен по лемме 1.
Осталось рассмотреть другой случай — когда до и после выполнения было полным. Обозначим множество после выполнения как
Так как изменяет только посредством операции , достаточно доказать, что сохраняет инвариант 3.
Анализ операции Relink
Операция переподвешивает узел к .
Пусть . Следовательно, до переподвешивания , а после переподвешивания . Таким образом, при переподвешивании может только увеличиться. Тем временем остается неизменным, ведь меняет ранг корня только тогда, когда дерево стало сокращенным, а сейчас мы рассматриваем только полные деревья. Из этого вытекает:
Итак, операция сохраняет инвариант 3, следовательно — операция сохраняет инвариант 3.
Delete
Пусть для множества инвариант 3 выполняется.
Если после выполнения стало сокращенным, то инвариант 3 сохранен по лемме 1.
Осталось рассмотреть случай, когда до и после выполнения было полным. Обозначим множество после выполнения как
Так как операция и обмен элементами между узлами не меняют структуры дерева, достаточно рассмотреть операцию .
Анализ операции DeleteLeaf
Пусть — удаляемый элемент, .
- Если , то обозначим . Мы удаляем и отсоединяем его братьев, их суммарное значение не больше . Потом мы подвешиваем братьев к — их суммарное значение становится . Итого, суммарное изменение значения не меньше
следовательно,
меняет только когда дерево становится сокращенным, а мы рассматриваем только полные, следовательно — не меняется, следовательно:
- Если Если , то обозначим . Обозначим некоторого брата , не являющегося листом, как . Мы удаляем и переподвешиваем сыновей , следовательно суммарное значение дерева сначала убывает на не более чем а после увеличивается на . Итого, суммарное изменение значения не меньше чем
следовательно
а так как , то
Итак, операция сохраняет инвариант 3, а значит, и операция сохраняет его.
Выводы
| Лемма: |
В вышеописанной структуре данных инвариант 3 сохраняется до и после каждой операции |
| Доказательство: |
| Изначально дерево является сокращенным и инвариант 3 выполняется в нем по лемме 1; каждая последующая операция сохраняет инвариант — лемма доказана. |
- Следствие 1
- Высота дерева никогда не превышает , следовательно операция занимает в худшем случае.
- Следствие 2
- занимает в среднем[2].
