СНМ с операцией удаления за О(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
Реализуем процедуру — переподвешивание элемента к его "дедушке" с сохранением инвариантов и структуры списков.
- Удалим из и вставим его в следующим образом:
- Если имеет брата справа от себя, вставим его в сразу слева от
- Иначе (если — крайний правый сын ) — вставим сразу справа от
- Обновим следующим образом:
- Если — крайний правый сын , то на предыдущем шаге мы вставили его в список детей сразу после , следовательно — порядок обхода вершин из в глубину не изменился. Значит, нам не нужно менять .
- В противном случае нам нужно поместить участок , соответствующий поддереву , перед . Этот участок — полуинтервал , где — сосед справа. Вырежем его и вставим перед .
- Если после этого стал листом, присвоим и удалим из корня дерева.
- Если после этого корня стал пустым, присвоим
Очевидно, что выполняется за
Операция Find
Реализуем собственно операцию :
- Пусть — вершина дерева, ассоциированная с элементом
- Пока , выполняем:
