Изменения

Амортизационный анализ сплей-дерева проводится с помощью метода потенциалов. Потенциалом рассматриваемого дерева назовём сумму рангов его вершин. Ранг вершины <tex>vx</tex> — это величина, обозначаемая <tex>r(vx)</tex> и равная <tex>\log_2 C(vx)</tex>, где <tex>C(vx)</tex> — количество вершин в поддереве с корнем в <tex>vx</tex>.

Амортизированное время операции splay вершины <tex>vx</tex> в дереве с корнем <tex>t</tex> не превосходит <tex>3r(t) - 3r(vx) + 1</tex>

Проанализируем каждый шаг операции splay. Пусть <tex>r'</tex> и <tex>r</tex> — ранги вершин после шага и до него соответственно, <tex>up</tex> — предок вершины <tex>vx</tex>, а <tex>wg</tex> — предок <tex>up</tex> (если есть).

'''Zig'''. Поскольку выполнен один поворот, то время амортизированное время выполнения шага <tex>T = 1 + r'(vx) + r'(up) - r(vx) - r(up)</tex> (поскольку только у вершин <tex>vx</tex> и <tex>up</tex> меняется ранг). Ранг вершины <tex>up</tex> уменьшился, поэтому <tex>T \le 1 + r'(vx) - r(vx)</tex>. Ранг вершины <tex>vx</tex> увеличился, поэтому <tex>r'(vx) - r(vx) \ge 0</tex>. Следовательно, <tex>T \le 1 + 3r'(vx) - 3r(vx)</tex>.

'''Zig-zig'''. Выполнено два поворота, амортизированное время выполнения шага <tex>T = 2 + r'(vx) + r'(up) + r'(wg) - r(up) - r(vx) - r(wg)</tex>. Поскольку после поворотов поддерево с корнем в <tex>vx</tex> будет содержать все вершины, которые были в поддереве с корнем в <tex>wg</tex> (и только их), поэтому <tex>r'(vx) = r(wg)</tex>. Используя это равенство, получаем: <tex>T = 2 + r'(up) + r'(wg) - r(vx) - r(up) \le 2 + r'(up) + r'(wg) - 2r(vx)</tex>, поскольку <tex>r(vx) \le r(up)</tex>.

Далее, так как <tex>r'(up) \le r'(vx)</tex>, получаем, что <tex>T \le 2 + r'(vx) + r'(wg) - 2r(vx)</tex>.

Мы утверждаем, что эта сумма не превосходит <tex>3(r'(vx) - r(vx))</tex>, то есть, что <tex>r(vx) + r'(wg) - 2r'(vx) \le -2</tex>. Преобразуем полученное выражение следующим образом: <tex>(r(vx) - r'(vx)) + (r'(wg) - r'(vx)) = \log_2 \frac{C(vx)}{C'(vx)} + \log_2 \frac{C'(wg)}{C'(vx)}</tex>.

Из рисунка видно, что <tex>C'(wg) + C(vx) \le C'(vx)</tex>, значит, сумма выражений под логарифмами не превосходит единицы. Далее, рассмотрим сумму логарифмов <tex>\log_2 x a + \log_2 y b = \log_2 xyab</tex>. При <tex>x a + y b \le 1</tex> произведение <tex>xyab</tex> по неравенству между средними не превышает <tex>1/4</tex>. А поскольку логарифм - функция возрастающая, то <tex>\log_2 xy ab \le -2</tex>, что и является требуемым неравенством.

'''Zig-zag'''. Выполнено два поворота, амортизированное время выполнения шага <tex>T = 2 + r'(vx) + r'(up) + r'(wg) - r(vx) - r(up) - r(wg)</tex>. Поскольку <tex>r'(vx) = r(wg)</tex>, то <tex>T = 2 + r'(up) + r'(wg) - r(vx) - r(up)</tex>. Далее, так как <tex>r(vx) \le r(up)</tex>, то <tex>T \le 2 + r'(up) + r'(wg) - 2r(vx)</tex>.

Мы утверждаем, что эта сумма не превосходит <tex>2(r'(vx) - r(vx))</tex>, то есть, что <tex>r'(up) + r'(wg) - 2r'(vx) \le -2</tex>. Но, поскольку <tex>r'(up) + r'(wg) - 2r'(vx) = \log_2 \frac{C'(up)}{C'(vx)} + \log_2 \frac{C'(wg)}{C'(vx)} \le -2</tex> - аналогично доказанному ранее, что и требовалось доказать.

Итого, получаем, что амортизированное время шага zig-zag не превосходит <tex>2(r'(vx) - r(vx)) \le 3(r'(vx) - r(vx))</tex>.

Поскольку за время выполнения операции splay выполняется не более одного шага типа zig, то суммарное время не будет превосходить <tex>3r(t) - 3r(vx) + 1</tex>, поскольку утроенные ранги промежуточных вершин сокращаются (входят в сумму как с плюсом, так и с минусом).