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