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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация операции Makeset)
(Реализация операции Union)
Строка 64: Строка 64:
  
 
=== Реализация операции Union ===
 
=== Реализация операции Union ===
Пусть <tex> T_A, T_B </tex> - деревья, реализующие множества <tex>A</tex> и <tex>B</tex> соответственно.
+
Пусть <tex> T_A, T_B </tex> {{---}} деревья, реализующие множества <tex>A</tex> и <tex>B</tex> соответственно.
Пусть размер одного из деревьев меньше 4; не умаляя общности - <tex>size(T_B) < 4</tex>. Тогда действуем следующим образом:
+
Пусть размер одного из деревьев меньше 4; не умаляя общности {{---}} <tex>size(T_B) < 4</tex>. Тогда действуем следующим образом:
 
# <tex>\forall v \in T_B : \: p(v) := root(T_A), \: rank(v) := 0</tex>
 
# <tex>\forall v \in T_B : \: p(v) := root(T_A), \: rank(v) := 0</tex>
 
# <tex> rank(root(T_A)) := max \: \{ rank(root(T_A)), 1 \: \}</tex>
 
# <tex> rank(root(T_A)) := max \: \{ rank(root(T_A)), 1 \: \}</tex>

Версия 10:25, 11 июня 2014

Реализация системы непересекающихся множеств с помощью леса корневых деревьев не поддерживает операцию удаления элемента из множества. Приведенная ниже модификация этой структуры данных вводит поддержку операции удаления за истинную [math]O(1)[/math], сохраняя асимптотику для операций [math]\mathrm{ Union } [/math] и [math]\mathrm{Find}[/math] и потребление памяти [math]O(n)[/math].

Введение

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

  • [math]\mathrm {Makeset(x)}[/math] — создать новое множество из 1 элемента [math]x [/math]. Время: [math]O(1)[/math]
  • [math]\mathrm {Union(A, B)}[/math] — объединить множества A и B в одно. Время: [math] O(1) [/math], без учета времени на операцию [math]find[/math], которая используется, если множества A и B заданы своими произвольными представителями.
  • [math]\mathrm {Find(x)}[/math] — найти множество, в котором содержится элемент [math] x [/math]. Время; [math]O(\log {n})[/math] в худшем случае, [math]O(\alpha(n))[/math] — в среднем ([math]\alpha(n)[/math] — обратная функция Аккермана), где n — размер множества.
  • [math]\mathrm{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]O(n) [/math] поддеревьев этой вершины. Однако, если вершина является листом, то ее можно удалять совершенно безболезненно.
Соображение 1: Пусть мы умеем менять произвольные вершины местами за [math]O(1)[/math]. Тогда для удаления некоторой вершины достаточно поменять ее местами с каким-нибудь листом и удалить этот лист.
Соображение 2: Пусть мы умеем находить какой-нибудь лист (неважно, какой именно) в дереве за [math]O(1)[/math]. Тогда, по соображению 1, мы уже умеем удалять произвольный элемент из дерева за [math]O(1)[/math]
Все дальнейшие действия направлены на то, чтобы поддержать эти 2 операции, не испортив при этом асимптотику всех остальных.

Реализация

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

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

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


Последнее нововведение, очевидно, позволит нам менять элементы в дереве местами за [math]O(1)[/math].
Первые три необходимы для нахождения листа в дереве (как оказывается, это гораздо более нетривиальная задача)
Введем также следующие определения:


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


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


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

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

Реализация операции Makeset

Тривиально:

  1. Создадим узел [math]v[/math] и свяжем его с элементом [math]x[/math]. Установим: [math]p(v) := v, rank(v) := 0[/math]
  2. Создадим для вершины [math]v[/math] пустые списки [math]\mathrm{NL_{LIST}}[/math] и [math]\mathrm{C_{LIST}}[/math].
  3. Создадим [math]\mathrm{DFS_{LIST}}[/math] с одним элементом — вершина [math]v[/math]

Очевидно, что операция соблюдает инварианты и выполняется за [math]O(1)[/math]

Реализация операции Union

Пусть [math] T_A, T_B [/math] — деревья, реализующие множества [math]A[/math] и [math]B[/math] соответственно. Пусть размер одного из деревьев меньше 4; не умаляя общности — [math]size(T_B) \lt 4[/math]. Тогда действуем следующим образом:

  1. [math]\forall v \in T_B : \: p(v) := root(T_A), \: rank(v) := 0[/math]
  2. [math] rank(root(T_A)) := max \: \{ rank(root(T_A)), 1 \: \}[/math]
  3. Присоединим [math]\mathrm{ DFS_{LIST}} [/math] и [math]\mathrm{C_{LIST}}[/math] для [math]T_B [/math] в конец [math]\mathrm{ DFS_{LIST}} [/math] и [math]\mathrm{C_{LIST}}[/math] для [math]T_A[/math]

Теперь рассмотрим случай, когда размеры обоих деревьев больше 4. Примем, не умаляя общности, что [math]rank(root(T_A)) \geq rank(root(T_B))[/math]. Тогда:

  1. [math]p(root(T_B)) := root(T_A)[/math], и если [math]rank(root(T_A)) = rank(root(T_B))[/math], увеличим [math]rank(root(T_A))[/math] на 1.
  2. Вставим [math]root(T_B)[/math] в начала [math]\mathrm{ N_{LIST}} [/math] и [math]\mathrm{C_{LIST}}[/math] для [math]T_A[/math]
  3. Вставим [math]\mathrm{ DFS_{LIST}} [/math] для [math]T_B [/math] в [math]\mathrm{ DFS_{LIST}} [/math] для [math]T_A [/math] сразу после [math]root(T_A)[/math]
  4. Сделаем [math]\mathrm{ N_{LIST}} [/math] для [math]T_B [/math] пустым. (Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную)

Если в качестве идентификаторов множеств нам переданы произвольные представители этих множеств, нам придется запустить процедуру [math]\mathrm {Find}[/math] для каждого из них, чтобы найти корни деревьев. Без учета вызова процедуры [math]\mathrm {Find}[/math] мы сделаем [math]O(1)[/math] операций.

Реализация операции Find

В нашей реализации операции [math]\mathrm {Find}[/math] вместо уже известного нам метода сжатия путей (path compressing) мы будем использовать разделение путей (path splitting). Он заключается в том, чтобы при выполнении операции [math]\mathrm {Find}[/math] перевешивать элемент, от которого мы вызвались, не сразу к корню, а к собственному "дедушке". Такой метод сокращения пути приводит к той же амотризационной оценке для функции [math]\mathrm {Find}[/math][1], несмотря на то, что интуитивно кажется более медленным. Мы будем использовать именно разделение путей, потому что это серьезно упрощает поддержку списков и инвариантов.

Операция Relink

Реализуем процедуру [math] \mathrm { Relink(x) } [/math] — переподвешивание элемента [math]x[/math] к его "дедушке" с сохранением инвариантов и структуры списков.

  1. Удалим [math] x [/math] из [math] \mathrm{C_{LIST}} \; p(x)[/math] и вставим его в [math] \mathrm{C_{LIST}} \; p(p(x))[/math] следующим образом:
    • Если [math]x[/math] имеет брата справа от себя, вставим его в [math] \mathrm{C_{LIST}} \; p(p(x))[/math] сразу слева от [math] p(x) [/math]
    • Иначе (если [math] x [/math] — крайний правый сын [math]p(x)[/math]) — вставим [math] x [/math] сразу справа от [math] p(x) [/math]
  2. Обновим [math] \mathrm {DFS_{LIST}} [/math] следующим образом:
    • Если [math]x[/math] — крайний правый сын [math]p(x)[/math], то на предыдущем шаге мы вставили его в список детей [math]p(p(x))[/math] сразу после [math]p(x)[/math], следовательно — порядок обхода вершин из [math] p(p(x)) [/math] в глубину не изменился. Значит, нам не нужно менять [math] \mathrm {DFS_{LIST}} [/math].
    • В противном случае нам нужно поместить участок [math] \mathrm {DFS_{LIST}} [/math], соответствующий поддереву [math]x[/math], перед [math]p(x) [/math]. Этот участок — полуинтервал [math][x, l)[/math], где [math]l[/math] — сосед [math]x[/math] справа. Вырежем его и вставим перед [math]p(x) [/math].
  3. Если после этого [math] p(x) [/math] стал листом, присвоим [math] rank(p(x)) := 0 [/math] и удалим [math] p(x) [/math] из [math]\mathrm{NL_{LIST}}[/math] корня дерева.
  4. Если после этого [math]\mathrm{NL_{LIST}}[/math] корня стал пустым, присвоим [math] rank(root) := 1 [/math]

Очевидно, что [math]\mathrm{Relink} [/math] выполняется за [math]O(1)[/math]

Операция Find

Реализуем собственно операцию [math]Find(a)[/math]:

  1. Пусть [math]x[/math] — вершина дерева, ассоциированная с элементом [math]a[/math]
  2. Пока [math]p(x) \neq root[/math], выполняем:
    1. [math]t := p(x)[/math]
    2. [math]Relink(x)[/math]
    3. [math]x := t[/math]

Примечания

Ссылки