СНМ с операцией удаления за О(1)

Реализация системы непересекающихся множеств с помощью леса корневых деревьев не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за О(1) в худшем случае, сохраняя асимптотику для операций Union и Find и потребление памяти O(n).

Введение

Наша структура данных должна поддерживать следующие операции:

• [math]makeset(x)[/math] - создать новое множество из 1 элемента [math]x [/math]. Время: [math]O(1)[/math]
• [math]union(A, B)[/math] - объединить множества A и B в одно. Время: [math] O(1) [/math], без учета времени на операцию [math]find[/math], которая используется, если множества A и B заданы своими произвольными представителями.
• [math]find(x)[/math] - найти множество, в котором содержится элемент [math] x [/math]. Время; [math]O(log n)[/math] в худшем случае, [math]O(\alpha(n))[/math] - в среднем ([math]\alpha(n)[/math] - обратная функция Аккермана), где n - размер множества.
• [math]delete(x)[/math] - удалить элемент x из содержащего его множества. Время: O(1)

В дальнейшем мы будем использовать следующие понятия и обозначения:

• [math]size(A)[/math] - размер множества A (количество элементов в нем).
• [math]root(T_A)[/math] - корень дерева [math]T_A[/math]
• [math]h(v)[/math] - высота вершины [math]v[/math]: если [math]v[/math] является листом, то [math]h(v) = 0[/math], иначе [math]h(v) = max ё\ h(w) | w - \mathrm{ child of } v \} [/math].
• [math]p(v)[/math] - родитель вершины [math]v[/math]. Если [math]v[/math] - корень, то считаем, что [math]p(v) = v[/math]
• [math]rank(v)[/math] - ранг вершины, некоторая верхняя оценка на ее высоту.

Как и в обычной реализации, выполнено следующее: [math]rank(v) \lt rank(p(v))[/math]

Реализация

Расширение структуры данных

Расширим лес корневых деревьев следующим образом:

• Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список [math] \mathrm{C_{list}} [/math] ее детей. Будем считать, что дети упорядочены по направлению списка слева направо.
• Для корня каждого дерева храним двусвязный список [math] \mathrm{NL_{list}} [/math] его детей, не являющихся листьями.
• Для каждого дерева (включая поддеревья) храним циклический двусвязный список [math] \mathrm{DFS_{list}} [/math] его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.
• Разделим понятия вершина дерева и элемент множества:
  • вершиной дерева назовем объект, содержащий ссылки [math]next[/math], [math]prev[/math] и [math]head[/math] (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине элемент множества;
  • элемент множества - объект, содержащий значение элемента и ссылку на соотв. вершину дерева.

Введем также следующие определения:

Определение:

Дерево, либо состоящее ровно из одной вершины, либо же из 1 вершины ранга 1 и листьев ранга 0, называется сокращенным (reduced)

Определение:

Дерево называется полным, если каждый из его узлов либо является листом с рангом 0, либо имеет не менее 3 детей.

В нашей структуре данных будет поддерживаться следующий инвариант: дерево является либо только полным, либо только сокращенным. Этот инвариант влечет за собой очевидные следствия:

• Все деревья (и поддеревья) размера < 4 - сокращенные, а >= 4 - полные
• Каждая вершина, среди детей которой есть хотя бы 1 нелистовая вершина, имеет не менее 3 детей (это не позволяет дереву вытягиваться в бамбук, например)