116
правок
Изменения
→Анализ
Операция <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 k - 1</tex>. Следовательно, до переподвешивания <tex>val(x) = \left( \frac{3}{2} \right)^{k - 1}</tex>, а после переподвешивания <tex>val(x) \leq \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 VAL(A) \geq 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) \leq 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 VAL(A)</tex></center><br>
<tex>\mathrm{Delete} </tex> меняет <tex> rank(A) </tex> только когда дерево становится сокращенным, а мы рассматриваем только полные, следовательно {{---}} <tex> rank(A) </tex> не меняется, следовательно:
<br><center><tex>VAL(A') \geq VAL(A) \geq 2^{rank(A)} = 2^{rank(A')}</tex></center><br>
* Если Если <tex>y = root</tex>, то обозначим <tex>k = rank(y) \Rightarrow rank(x) \leq k - 1</tex>. Обозначим некоторого брата <tex>x</tex>, не являющегося листом, как <tex>c \Rightarrow rank(c) \leq 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 VAL(A)</tex>,</center>
а так как <tex>2^{rank(A)} = 2^{rank(A')}</tex>, то
<center><tex>VAL(A') \geq VAL(A) \geq 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
: Высота дерева никогда не превышает <tex>O(\log {n})</tex>, следовательно операция <tex>\mathrm{Find}</tex> занимает <tex>O(\log {n})</tex> в худшем случае.
; Следствие 2
: <tex>\mathrm{Find}</tex> занимает <tex>O(\alpha (n))</tex> в среднем.
= Примечания =
