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