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

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

Содержание

Описание [ править ]

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

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

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

[math]size(A)[/math] — размер множества [math]A[/math] (количество элементов в нем).
[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 \> + 1[/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] .

Все дальнейшие усилия направлены на то, чтобы поддержать эти [math]2[/math] операции, не испортив при этом асимптотику всех остальных.

Реализация [ править ]

Расширение структуры данных [ править ]

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

Модификации для 1-го соображения [ править ]

Разделим понятия вершина дерева и элемент множества:

вершиной дерева назовем объект, содержащий ссылки [math]next[/math] , [math]prev[/math] и [math]head[/math] (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине элемент множества;
элемент множества — объект, содержащий значение элемента и ссылку на соотв. вершину дерева.

Это нововведение, очевидно, позволит менять элементы в дереве местами за [math]O(1)[/math] .

Модификации для 2-го соображения [ править ]

Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список [math] \mathrm [/math] ее детей. Будем считать, что дети упорядочены по направлению списка слева направо.
Для корня каждого дерева храним двусвязный список [math] \mathrm [/math] его детей, не являющихся листьями.
Для каждого дерева (включая поддеревья) храним циклический двусвязный список [math] \mathrm [/math] его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.

Эти три нововведения необходимы для нахождения листа в дереве (как оказывается, это гораздо более нетривиальная задача).

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

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

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

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

Все деревья (и поддеревья) размера [math]\lt 4[/math] — сокращенные, а [math]\geqslant 4[/math] — полные
Каждая вершина, среди детей которой есть хотя бы [math]1[/math] нелистовая вершина, имеет не менее [math]3[/math] детей (это не позволяет дереву вытягиваться в бамбук, например)

Реализация операции Makeset [ править ]

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

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

Реализация операции Union [ править ]

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

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

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

[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] на [math]1[/math] .
Вставим [math]root(T_B)[/math] в начало [math]\mathrm< N_> [/math] и [math]\mathrm[/math] для [math]T_A[/math] .
Вставим [math]\mathrm< DFS_> [/math] для [math]T_B [/math] в [math]\mathrm< DFS_> [/math] для [math]T_A [/math] сразу после [math]root(T_A)[/math] .
Сделаем [math]\mathrm< N_> [/math] для [math]T_B [/math] пустым. (Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную)

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

Реализация операции Find [ править ]

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

Операция Relink [ править ]

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

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

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

Операция Find [ править ]

Реализуем собственно операцию [math]\mathrm[/math] :

Пусть [math]x[/math] — вершина дерева, ассоциированная с элементом [math]a[/math]
Пока [math]p(x) \neq root[/math] , выполняем:
1. [math]t = p(x)[/math]
2. [math]Relink(x)[/math]
3. [math]x = t[/math]
Реализация операции Delete [ править ]
Сначала разработаем процедуру удаления узла из дерева, у которого [math]size(T) \leqslant 4[/math] — удаление из такого дерева даст нам сокращенное дерево. Назовем эту процедуру [math]\mathrm [/math] .
Операция ReducedTreeDelete [ править ]
1. Если дерево не сокращенное, сделаем его сокращенным, просто переподвесив все вершины к корню. Так как дерево маленькое — [math]size(T) \leqslant 4[/math] — операция выполняется за [math]O(1)[/math]
2. Если [math]a[/math] ассоциирован с листом, просто удалим этот лист.
3. Иначе [math]a[/math] ассоциирован с корнем: просто поменяем [math]a[/math] местами с элементом из любого листа (любого сына корня) и удалим этот лист.
Теперь подумаем, как удалять элемент из полного дереве размера больше [math]4[/math] . После удаления дерево должно остаться полным.

Нам необходимо найти некоторый лист дерева, из которого мы удаляем элемент. Реализуем для этого процедуру [math]\mathrm[/math] .
Операция FindLeaf [ править ]
1. Пусть элемент [math]a[/math] ассоциирован с вершиной [math]x[/math] .
2. Если [math]x[/math] — лист, задача решена.
3. Если [math]x[/math] — корень дерева, то он является первым в [math]\mathrm[/math] . Но при обходе в глубину последняя пройденная вершина всегда является листом, а значит — вершина, идущая в [math]\mathrm[/math] перед корнем, является листом. Возвращаем ее.
4. В противном случае:
  - Если [math]x[/math] имеет брата справа — [math]r[/math] , то перед тем как обойти [math]r[/math] поиском в глубину, мы обошли самый правый лист поддерева [math]x[/math] . Следовательно, нужный нам лист — [math]\mathrm[r].prev[/math] .
  - Иначе [math]x[/math] имеет брата слева — [math]l[/math] , и по аналогичным рассуждениям листом является [math]\mathrm[x].prev[/math] .
Итак, мы нашли некоторый лист дерева за [math]O(1)[/math] . Теперь нам нужно просто уметь его удалять, но так, чтобы инварианты и структура списков сохранялись.
Операция DeleteLeaf [ править ]
Пусть [math]x[/math] — удаляемый лист.
1. Извлекаем [math]x[/math] из [math]\mathrm \; p(x) [/math] и из [math]\mathrm[/math]
2. Удаляем узел [math]x[/math]
Следующие [math]2[/math] шага обеспечивают сохранение полноты дерева
1. Если [math]p(x) \neq root(T)[/math] , вызовем [math]\mathrm[/math] для 2 самых правых детей [math]p(x)[/math]
2. Иначе найдем среди детей [math]p(x)[/math] узел, не являющийся листом (с помощью [math]\mathrm[/math] ), и вызовем [math]\mathrm[/math] для [math]3[/math] его самых правых детей.
Так как операция [math]\mathrm[/math] сохраняет полноту дерева и выполняется за [math]O(1)[/math] , [math]\mathrm[/math] , очевидно, обладает теми же свойствами.

Итак, соберем воедино операцию [math]\mathrm[/math] :
Операция Delete [ править ]
Пусть элемент [math]a[/math] ассоциирован с вершиной [math]x[/math]
1. Если [math]size(T) \leqslant 4[/math] , вызываем [math]\mathrm[/math]
2. Иначе:
  1. [math]l = \mathrm [/math]
  2. Поменяем элементы в [math]x[/math] и [math]l[/math] местами.
  3. [math]\mathrm[/math]
  Анализ [ править ]
  Основные положения [ править ]
  Докажем верхнюю оценку стоимости операции [math]\mathrm[/math] в [math]O(\log )[/math] .
  
  Нам необходимо доказать, что все определенные нами операции — [math]\mathrm[/math] , [math]\mathrm[/math] , [math]\mathrm[/math] и [math]\mathrm[/math] — поддерживают следующий инвариант:
  
  Так как в [math]T_A[/math] есть [math]|A|[/math] вершин и [math]val(v) \leqslant \left(\frac \right)^[/math] , то:
  
  [math] 2^ \leqslant VAL(A) \leqslant |A| \left(\frac \right)^ \newline \newline |A| \geqslant \frac = \left( \frac \right)^ \newline \newline rank(A) \leqslant \log_< \frac > < (|A|) >= O(\log ) = O(\log) [/math]
  
  Если [math]h(T_A) = 0[/math] (т. е. дерево состоит только из корня), то [math]VAL(A) = \left( \frac \right)^ = 1 [/math] и [math] 2^ = 2^0 = 1 \Rightarrow VAL(A) = 2^ [/math] .
  
  Докажем теперь, что каждая из операций сохраняет инвариант 3.
  Makeset [ править ]
  Т. к. операция [math]\mathrm[/math] создает сокращенное дерево, то по лемме 1 [math]\mathrm[/math] сохраняет инвариант 3
  Union [ править ]
  Пусть для множеств [math]A[/math] и [math]B[/math] инвариант 3 выполняется.
  
  Пусть [math]C = \mathrm[/math] . Пусть, не умаляя общности, [math]rank(A) \gt rank(B)[/math] . Тогда мы подвесим [math]T_B[/math] к корню [math]T_A[/math] , и [math]rank(C)[/math] будет равным [math]rank(A)[/math] , и следовательно,
  
  [math]VAL(C) \gt VAL(A) \geqslant 2^ = 2^[/math]
  
  Пусть теперь [math]rank(A) = rank(B)[/math] , тогда [math]rank(C) = rank(A) + 1[/math] и имеем:
  
  Следовательно, операция [math]\mathrm[/math] сохраняет инвариант 3.
  Find [ править ]
  Пусть для множества [math]A[/math] инвариант 3 выполняется.
  
  Операция [math]\mathrm[/math] изменяет дерево [math]T_A[/math] . Если после выполнения [math]\mathrm \; T_A[/math] стало сокращенным, то инвариант 3 сохранен по лемме 1.
  
  Осталось рассмотреть другой случай — когда до и после выполнения [math]\mathrm \; T_A[/math] было полным. Обозначим множество [math]A[/math] после выполнения [math]\mathrm[/math] как [math]A'[/math]
  
  Так как [math]\mathrm[/math] изменяет [math]T_A[/math] только посредством операции [math]\mathrm[/math] , достаточно доказать, что [math]\mathrm[/math] сохраняет инвариант 3.
  Анализ операции Relink [ править ]
  Операция [math]\mathrm[/math] переподвешивает узел [math]x[/math] к [math]p(p(x))[/math] .
  
  Пусть [math]y = p(x), g = p(y), k = rank(g) \Rightarrow rank(y) \leqslant k - 1[/math] . Следовательно, до переподвешивания [math]val(x) = \left( \frac \right)^[/math] , а после переподвешивания [math]val(x) \leqslant \left( \frac \right)^[/math] . Таким образом, при переподвешивании [math]x \; VAL(A)[/math] может только увеличиться. Тем временем [math]rank(A)[/math] остается неизменным, ведь [math]\mathrm[/math] меняет ранг корня только тогда, когда дерево стало сокращенным, а сейчас мы рассматриваем только полные деревья. Из этого вытекает:
  
  [math]VAL(A') \geqslant VAL(A) \geqslant 2^ = 2^[/math]
  
  Итак, операция [math]\mathrm[/math] сохраняет инвариант 3, а значит, и операция [math]\mathrm [/math] сохраняет его.
  📎📎📎📎📎📎📎📎📎📎

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

Содержание

Описание [ править ]

Идея [ править ]

Реализация [ править ]

Анализ [ править ]