304
правки
Изменения
→Анализ операции splay
Мы утверждаем, что эта сумма не превосходит <tex>3(r'(v) - r(v))</tex>, то есть, что <tex>r(v) + r'(w) - 2r'(v) \le -2</tex>. Преобразуем полученное выражение следующим образом: <tex>(r(v) - r'(v)) + (r'(w) - r'(v)) = \log_2 \frac{C(v)}{C'(v)} + \log_2 \frac{C'(w)}{C'(v)}</tex>.
Из рисунка видно, что <tex>C'(w) + C(v) \le C'(v)</tex>, значит, сумма выражений под логарифмами не превосходит единицы. Далее, рассмотрим сумму логарифмов <tex>\log_2 x + \log_2 y = \log_2 xy</tex>. При <tex>x + y \le 1</tex> произведение <tex>xy</tex> по неравенству между средними не превышает <tex>1/4</tex>. А поскольку логарифм - функция возрастающая, то <tex>\log_2 xy \le -2</tex>, что и является требуемым неравенством.
'''Zig-zag'''. Выполнено два поворота, амортизированное время выполнения шага <tex>T = 2 + r'(v) + r'(u) + r'(w) - r(v) - r(u) - r(w)</tex>. Поскольку <tex>r'(v) = r(w)</tex>, то <tex>T = 2 + r'(u) + r'(w) - r(v) - r(u)</tex>. Далее, так как <tex>r(v) \le r(u)</tex>, то <tex>T \le 2 + r'(u) + r'(w) - 2r(v)</tex>.
Поскольку за время выполнения операции splay выполняется не более одного шага типа zig, то суммарное время не будет превосходить <tex>3r(t) - 3r(v) + 1</tex>, поскольку утроенные ранги промежуточных вершин сокращаются (входят в сумму как с плюсом, так и с минусом).
==Литература==
# Daniel Sleator, Robert Tarjan "A data structure for dynamic trees"
