Изменения

=== Анализ операции 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 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>

= Примечания =