116
правок
Изменения
Нет описания правки
;Соображение 2 : Пусть мы умеем находить какой-нибудь лист (неважно, какой именно) в дереве за <tex>O(1)</tex>. Тогда, по соображению 1, мы уже умеем удалять произвольный элемент из дерева за <tex>O(1)</tex>
<br />
Все дальнейшие усилия направлены на то, чтобы поддержать эти <tex>2 </tex> операции, не испортив при этом асимптотику всех остальных.
== Реализация ==
{{Определение
|id=def_reduced_tree
|definition=Дерево, либо состоящее ровно из одной вершины, либо же из <tex>1 </tex> вершины ранга <tex>1 </tex> и листьев ранга <tex>0</tex>, называется '''сокращенным''' (англ. ''reduced'')
}}
{{Определение
|id=def_full_tree
|definition=Дерево называется '''полным''' (англ. ''full''), если каждый из его узлов либо является листом с рангом <tex>0</tex>, либо имеет не менее <tex>3 </tex> детей.
}}
В нашей структуре данных будет поддерживаться следующий инвариант: '''дерево всегда полное или сокращенное'''.
Этот инвариант влечет за собой очевидные следствия:
* Все деревья (и поддеревья) размера <tex><4</tex> 4 - сокращенные, а <tex>\geqslant4</tex> 4 - полные* Каждая вершина, среди детей которой есть хотя бы <tex>1 </tex> нелистовая вершина, имеет не менее <tex>3 </tex> детей (это не позволяет дереву вытягиваться в бамбук, например)
=== Реализация операции Makeset ===
=== Реализация операции Union ===
Пусть <tex> T_A, T_B </tex> {{---}} деревья, реализующие множества <tex>A</tex> и <tex>B</tex> соответственно.
Пусть размер одного из деревьев меньше <tex>4</tex>; не умаляя общности {{---}} <tex>size(T_B) < 4</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>\mathrm{ DFS_{LIST}} </tex> и <tex>\mathrm{C_{LIST}}</tex> для <tex>T_B </tex> в конец <tex>\mathrm{ DFS_{LIST}} </tex> и <tex>\mathrm{C_{LIST}}</tex> для <tex>T_A</tex>
Теперь рассмотрим случай, когда размеры обоих деревьев больше <tex>4</tex>.
Примем, не умаляя общности, что <tex>rank(root(T_A)) \geqslant rank(root(T_B))</tex>. Тогда:
# <tex>p(root(T_B)) := root(T_A)</tex>, и если <tex>rank(root(T_A)) = rank(root(T_B))</tex>, увеличим <tex>rank(root(T_A))</tex> на <tex>1</tex>.
# Вставим <tex>root(T_B)</tex> в начала <tex>\mathrm{ N_{LIST}} </tex> и <tex>\mathrm{C_{LIST}}</tex> для <tex>T_A</tex>
# Вставим <tex>\mathrm{ DFS_{LIST}} </tex> для <tex>T_B </tex> в <tex>\mathrm{ DFS_{LIST}} </tex> для <tex>T_A </tex> сразу после <tex>root(T_A)</tex>
#* Если <tex>x</tex> {{---}} крайний правый сын <tex>p(x)</tex>, то на предыдущем шаге мы вставили его в список детей <tex>p(p(x))</tex> сразу после <tex>p(x)</tex>, следовательно {{---}} порядок обхода вершин из <tex> p(p(x)) </tex> в глубину не изменился. Значит, нам не нужно менять <tex> \mathrm {DFS_{LIST}} </tex>.
#* В противном случае нам нужно поместить участок <tex> \mathrm {DFS_{LIST}} </tex>, соответствующий поддереву <tex>x</tex>, перед <tex>p(x) </tex>. Этот участок {{---}} полуинтервал <tex>[x, l)</tex>, где <tex>l</tex> {{---}} сосед <tex>x</tex> справа. Вырежем его и вставим перед <tex>p(x) </tex>.
# Если после этого у <tex>p(x)</tex> осталось менее <tex>3 </tex> детей, проделаем шаги <tex>1 </tex> и <tex>2 </tex> и с ними тоже.
# Если после этого <tex> p(x) </tex> стал листом, присвоим <tex> rank(p(x)) := 0 </tex> и удалим <tex> p(x) </tex> из <tex>\mathrm{NL_{LIST}}</tex> корня дерева.
# Если после этого <tex>\mathrm{NL_{LIST}}</tex> корня стал пустым (это значит, что дерево стало сокращенным), присвоим <tex> rank(root) := 1 </tex>
# Иначе <tex>a</tex> ассоциирован с корнем: просто поменяем <tex>a</tex> местами с элементом из любого листа (любого сына корня) и удалим этот лист.
Теперь подумаем, как удалять элемент из полного дереве размера больше <tex>4</tex>. После удаления дерево должно остаться полным. <br/>
Нам необходимо найти некоторый лист дерева, из которого мы удаляем элемент. Реализуем для этого процедуру <tex>\mathrm{FindLeaf(a)}</tex>.
==== Операция FindLeaf ====
# Извлекаем <tex>x</tex> из <tex>\mathrm{C_{LIST}} \; p(x) </tex> и из <tex>\mathrm{DFS_{LIST}}</tex>
# Удаляем узел <tex>x</tex>
Следующие <tex>2 </tex> шага обеспечивают сохранение полноты дерева
# Если <tex>p(x) \neq root(T)</tex>, вызовем <tex>\mathrm{Relink}</tex> для 2 самых правых детей <tex>p(x)</tex>
# Иначе найдем среди детей <tex>p(x)</tex> узел, не являющийся листом (с помощью <tex>\mathrm{NL_{LIST}}</tex>), и вызовем <tex>\mathrm{Relink}</tex> для <tex>3 </tex> его самых правых детей.
Так как операция <tex>\mathrm{Relink}</tex> сохраняет полноту дерева и выполняется за <tex>O(1)</tex>, <tex>\mathrm{DeleteLeaf}</tex>, очевидно, обладает теми же свойствами.
{{Утверждение
|statement=
При выполнении '''инварианта 3 ''' высота дерева не превышает <tex>O(\log {n})</tex>
|proof=
Так как в <tex>T_A</tex> есть <tex>|A|</tex> вершин и <tex>val(v) \leqslant \left(\frac{3}{2} \right)^{rank(A)}</tex>, то: <br/>
|author=1
|statement=
Для всякого сокращенного дерева <tex>T_A</tex> '''инвариант 3 ''' выполняется
|proof=
Если <tex>h(T_A) = 0</tex> (т. е. дерево состоит только из корня), то <tex>VAL(A) = \left( \frac{3}{2} \right)^{0} = 1 </tex> и <tex> 2^{rank(A)} = 2^0 = 1 \Rightarrow VAL(A) = 2^{rank(A)} </tex>. <br/>
}}
Докажем теперь, что каждая из операций сохраняет '''инвариант 3'''.
=== Makeset ===
Т. к. операция <tex>\mathrm{Makeset}</tex> создает сокращенное дерево, то по '''лемме 1 ''' <tex>\mathrm{Makeset}</tex> сохраняет '''инвариант 3'''
=== Union ===
Пусть для множеств <tex>A</tex> и <tex>B</tex> '''инвариант 3 ''' выполняется. <br/>
Пусть <tex>C = \mathrm{Union(A, B)}</tex>. Пусть, не умаляя общности, <tex>rank(A) > rank(B)</tex>. Тогда мы подвесим <tex>T_B</tex> к корню <tex>T_A</tex>, и <tex>rank(C)</tex> будет равным <tex>rank(A)</tex>, и следовательно, <br/><br/><center><tex>VAL(C) > VAL(A) \geqslant 2^{rank(A)} = 2^{rank(C)}</tex></center><br/>
Пусть теперь <tex>rank(A) = rank(B)</tex>, тогда <tex>rank(C) = rank(A) + 1</tex> и имеем:
<br/><center><tex>VAL(C) > VAL(A) + VAL(B) \geqslant 2^{rank(A)} + 2^{rank(B)} = 2^{1 + rank(A)} = 2^{rank(C)} </tex></center><br/>
Следовательно, операция <tex>\mathrm{Union}</tex> сохраняет '''инвариант 3'''.
=== Find ===
Пусть для множества <tex>A</tex> '''инвариант 3 ''' выполняется. <br>Операция <tex>\mathrm{Find}</tex> изменяет дерево <tex>T_A</tex>. Если после выполнения <tex>\mathrm{Find} \; T_A</tex> стало сокращенным, то '''инвариант 3 ''' сохранен по '''лемме 1'''. <br/>
Осталось рассмотреть другой случай - когда до и после выполнения <tex>\mathrm{Find} \; T_A</tex> было полным. Обозначим множество <tex>A</tex> после выполнения <tex>\mathrm{Find}</tex> как <tex>A'</tex>
<br/> Так как <tex>\mathrm{Find}</tex> изменяет <tex>T_A</tex> только посредством операции <tex>\mathrm{Relink}</tex>, достаточно доказать, что <tex>\mathrm{Relink}</tex> сохраняет инвариант 3.
==== Анализ операции Relink ====
Операция <tex>\mathrm{Relink}</tex> переподвешивает узел <tex>x</tex> к <tex>p(p(x))</tex>. <br/> Пусть <tex>y = p(x), g = p(y), k = rank(g) \Rightarrow rank(y) \leqslant k - 1</tex>. Следовательно, до переподвешивания <tex>val(x) = \left( \frac{3}{2} \right)^{k - 1}</tex>, а после переподвешивания <tex>val(x) \leqslant \left( \frac{3}{2} \right)^{k}</tex>. Таким образом, при переподвешивании <tex>x \; VAL(A)</tex> может только увеличиться. Тем временем <tex>rank(A)</tex> остается неизменным, ведь <tex>\mathrm{Relink}</tex> меняет ранг корня только тогда, когда дерево стало сокращенным, а сейчас мы рассматриваем только полные деревья. Из этого вытекает: <br><center><tex>VAL(A') \geqslant VAL(A) \geqslant 2^{rank(A)} = 2^{rank(A')}</tex></center><br>
Итак, операция <tex>\mathrm{Relink}</tex> сохраняет '''инвариант 3''', следовательно {{---}} операция <tex>\mathrm{Find}</tex> сохраняет '''инвариант 3'''.
=== Delete ===
Пусть для множества <tex>A</tex> инвариант 3 выполняется. <br>
Если после выполнения <tex>\mathrm{Delete} \; T_A</tex> стало сокращенным, то '''инвариант 3 ''' сохранен по '''лемме 1'''. <br/>
Осталось рассмотреть случай, когда до и после выполнения <tex>\mathrm{Delete} \; T_A</tex> было полным. Обозначим множество <tex>A</tex> после выполнения <tex>\mathrm{Delete}</tex> как <tex>A'</tex><br/>
Так как операция <tex>\mathrm{FindLeaf}</tex> и обмен элементами между узлами не меняют структуры дерева, достаточно рассмотреть операцию <tex>\mathrm{DeleteLeaf}</tex>.
==== Анализ операции DeleteLeaf ====
Пусть <tex>x</tex> {{---}} удаляемый элемент, <tex>y = p(x)</tex>.
* Если <tex>y \neq root</tex>, то обозначим <tex>g = p(y), k = rank(g) \Rightarrow rank(y) \leqslant k - 1</tex>. Мы удаляем <tex>x</tex> и отсоединяем <tex>2 </tex> его братьев, их суммарное значение не больше <tex>3 \left( \frac {3} {2} \right) ^ {k - 1} </tex>. Потом мы подвешиваем <tex>2 </tex> братьев к <tex>g</tex> {{---}} их суммарное значение становится <tex>2 \left( \frac {3} {2} \right) ^ k </tex>. Итого, суммарное изменение значения не меньше <br><center><tex>-3 \left( \frac {3} {2} \right) ^ {k - 1} + 2 \left( \frac {3} {2} \right) ^ k = 0</tex>,</center><br>
следовательно,
<center><tex>VAL(A') \geqslant VAL(A)</tex></center><br>
<br><center><tex>VAL(A') \geqslant VAL(A) \geqslant 2^{rank(A)} = 2^{rank(A')}</tex></center><br>
* Если Если <tex>y = root</tex>, то обозначим <tex>k = rank(y) \Rightarrow rank(x) \leqslant k - 1</tex>. Обозначим некоторого брата <tex>x</tex>, не являющегося листом, как <tex>c \Rightarrow rank(c) \leqslant k - 1</tex>. Мы удаляем <tex>x</tex> и переподвешиваем <tex>3 </tex> сыновей <tex>c</tex>, следовательно суммарное значение дерева сначала убывает на не более чем <tex>\left( \frac {3} {2} \right) ^ k + 3 \left( \frac {3} {2} \right) ^ {k - 1}</tex> а после увеличивается на <tex>3 \left( \frac {3} {2} \right) ^ k </tex>. Итого, суммарное изменение значения не меньше чем
<center><tex> -\left( \frac {3} {2} \right) ^ k - 3 \left( \frac {3} {2} \right) ^ {k - 1} + 3 \left( \frac {3} {2} \right) ^ k</tex>,</center>
следовательно
<center><tex>VAL(A') \geqslant VAL(A) \geqslant 2^{rank(A)} = 2^{rank(A')}</tex></center><br>
Итак, операция <tex>\mathrm{DeleteLeaf}</tex> сохраняет '''инвариант 3''', а значит, и операция <tex>\mathrm{Delete} </tex> сохраняет его.
=== Выводы ===
|id=lemma_2
|statement=
В вышеописанной структуре данных '''инвариант 3 ''' сохраняется до и после каждой операции
|proof=
Изначально дерево является сокращенным и '''инвариант 3 ''' выполняется в нем по '''лемме 1'''; каждая последующая операция сохраняет инвариант {{---}} лемма доказана.
}}
; Следствие 1
