СНМ с операцией удаления за О(1)
Реализация системы непересекающихся множеств с помощью леса корневых деревьев не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за О(1) в худшем случае, сохраняя асимптотику для операций Union и Find и потребление памяти O(n).
Реализация
Расширение структуры данных
Расширим лес корневых деревьев следующим образом:
- Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список ее детей. Будем считать, что дети упорядочены по направлению списка слева направо.
- Для корня каждого дерева храним двусвязный список его детей, не являющихся листьями.
- Для каждого дерева (включая поддеревья) храним циклический двусвязный список его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.
- Разделим понятия вершина дерева и элемент множества:
- вершиной дерева назовем объект, содержащий ссылки , и (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине элемент множества;
- элемент множества - объект, содержащий значение элемента и ссылку на соотв. вершину дерева.
Введем также следующие определения:
| Определение: |
| Дерево, либо состоящее ровно из одной вершины, либо же из 1 вершины ранга 1 и листьев ранга 0, называется сокращенным (reduced) |
| Определение: |
| Дерево называется полным, если каждый из его узлов либо является листом с рангом 0, либо имеет не менее 3 детей. |
В нашей структуре данных будет поддерживаться следующий инвариант: дерево является либо только полным, либо только сокращенным.
Этот инвариант влечет за собой очевидные следствия:
- Все деревья (и поддеревья) размера < 4 - сокращенные, а >= 4 - полные
- Каждая вершина, среди детей которой есть хотя бы 1 нелистовая вершина, имеет не менее 3 детей (это не позволяет дереву вытягиваться в бамбук, например)
