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