Splay-дерево

Определение

Сплей-дерево (Splay-tree) — саморегулирующееся двоичное дерево поиска. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.

Основной идеей для сохранение баланса дерева является перетаскивание найденной вершины в корень после каждой операции поиска.

Операции со splay-деревом

Move to Root

Пусть [math] p(x) [/math] - предок вершины [math] x [/math]. Эвристика "Move to Root" совершает повороты вокруг ребра [math] \langle x, p(x) \rangle [/math], пока [math] x [/math] не окажется корнем дерева. Данный поворот аналогичен zig - повороту.

Splay

"Splay" так же как и "Move to Root" перетаскивает вершину в корень дерева, но при этом она использует другую последовательность поворотов. Пока [math] x [/math] не является корнем дерева выполняется следующее :

1. Zig. Если [math] p(x) [/math] - корень дерева, то совершаем один поворот вокруг ребра [math] \langle x, p(x) \rangle [/math], делая [math] x [/math] корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина [math] x [/math] была нечетной.

1. Zig-Zig. Если [math] p(x) [/math] - не корень дерева, а [math] x [/math] и [math] p(x) [/math] - оба левые или оба правые дети, то делаем поворот ребра [math] \langle p(x), p(p(x)) \rangle [/math], а затем поворот ребра [math] \langle x, p(x) \rangle [/math].

1. Zig-Zag. Если [math] p(x) [/math] - не корень дерева и [math] x [/math] - левый ребенок, а [math] p(x) [/math] - правый, или наоборот, то делаем поворот вокруг ребра [math] \langle x, p(x) \rangle [/math], а затем поворот нового ребра [math] \langle x, p(x) \rangle [/math], где [math] p(x) [/math] - новый родитель [math] x [/math].

Данная операция занимает [math] O(d) [/math] времени, где [math] d [/math] - длина пути от [math] x [/math] до корня. В результате этой операции [math] x [/math] становится корнем дерева, а расстояние до корня от каждой вершины сокращается примерно пополам, что связано с разделением случаев "zig-zig" и "zig-zag".

Merge

Merge([math]T_1[/math], [math]T_2[/math]). У нас есть два дерева [math]T_1[/math] и [math]T_2[/math], причём подразумевается, что все элементы первого дерева меньше элементов второго. Запускаем Splay от самого большого элемента в дереве [math]T_1[/math] (пусть это элемент [math]i[/math]). После этого корень [math]T_1[/math] содержит элемент [math]i[/math], при этом у него нет правого ребёнка. Делаем [math]T_2[/math] правым поддеревом [math]i[/math] и возвращаем полученное дерево.

Split

Split([math]i[/math], [math]T[/math]). Запускаем Splay от элемента [math]i[/math] и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем [math]i[/math].

Add

Add([math]i[/math], [math]T[/math]). Запускаем Split([math]i[/math], [math]T[/math]), который нам возвращает деревья [math]T_1[/math] и [math]T_2[/math], их подвешиваем к [math]i[/math] как левое и правое поддеревья соответственно.

Remove

Remove([math]i[/math], [math]T[/math]). Запускаем Splay от [math]i[/math]-го элемента и возвращаем Merge от его детей.

Анализ операции splay

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

Лемма:

Амортизированное время операции splay вершины [math]v[/math] в дереве с корнем [math]t[/math] не превосходит [math]3r(t) - 3r(v) + 1[/math]

Доказательство:

[math]\triangleright[/math]

Проанализируем каждый шаг операции splay. Пусть [math]r'[/math] и [math]r[/math] — ранги вершин после шага и до него соответственно, [math]u[/math] — предок вершины [math]v[/math], а [math]w[/math] — предок [math]u[/math] (если есть). Разберём случаи в зависимости от типа шага: Zig. Поскольку выполнен один поворот, то время амортизированное время выполнения шага [math]T = 1 + r'(v) + r'(u) - r(v) - r(u)[/math] (поскольку только у вершин [math]v[/math] и [math]u[/math] меняется ранг). Ранг вершины [math]u[/math] уменьшился, поэтому [math]T \le 1 + r'(v) - r(v)[/math]. Ранг вершины [math]v[/math] увеличился, поэтому [math]r'(v) - r(v) \ge 0[/math]. Следовательно, [math]T \le 1 + 3r'(v) - 3r(v)[/math]. Zig-zig. Выполнено два поворота, амортизированное время выполнения шага [math]T = 2 + r'(v) + r'(u) + r'(w) - r(u) - r(v) - r(w)[/math]. Поскольку после поворотов поддерево с корнем в [math]v[/math] будет содержать все вершины, которые были в поддереве с корнем в [math]w[/math] (и только их), поэтому [math]r'(v) = r(w)[/math]. Используя это равенство, получаем: [math]T = 2 + r'(u) + r'(w) - r(v) - r(u) \le 2 + r'(u) + r'(w) - 2r(v)[/math], поскольку [math]r(v) \le r(u)[/math]. Далее, так как [math]r'(u) \le r'(v)[/math], получаем, что [math]T \le 2 + r'(v) + r'(w) - 2r(v)[/math]. Мы утверждаем, что эта сумма не превосходит [math]3(r'(v) - r(v))[/math], то есть, что [math]r(v) + r'(w) - 2r'(v) \le -2[/math]. Преобразуем полученное выражение следующим образом: [math](r(v) - r'(v)) + (r'(w) - r'(v)) = \log_2 \frac{C(v)}{C'(v)} + \log_2 \frac{C'(w)}{C'(v)}[/math]. Из рисунка видно, что [math]C'(w) + C(v) \le C'(v)[/math], значит, сумма выражений под логарифмами не превосходит единицы. Далее, рассмотрим сумму логарифмов [math]\log_2 x + \log_2 y = \log_2 xy[/math]. При [math]x + y \le 1[/math] произведение [math]xy[/math] по неравенству между средними не превышает [math]1/4[/math]. А поскольку логарифм - функция возрастающая, то [math]\log_2 xy \le -2[/math], что и является требуемым неравенством. Zig-zag. Выполнено два поворота, амортизированное время выполнения шага [math]T = 2 + r'(v) + r'(u) + r'(w) - r(v) - r(u) - r(w)[/math]. Поскольку [math]r'(v) = r(w)[/math], то [math]T = 2 + r'(u) + r'(w) - r(v) - r(u)[/math]. Далее, так как [math]r(v) \le r(u)[/math], то [math]T \le 2 + r'(u) + r'(w) - 2r(v)[/math]. Мы утверждаем, что эта сумма не превосходит [math]2(r'(v) - r(v))[/math], то есть, что [math]r'(u) + r'(w) - 2r'(v) \le -2[/math]. Но, поскольку [math]r'(u) + r'(w) - 2r'(v) = \log_2 \frac{C'(u)}{C'(v)} + \log_2 \frac{C'(w)}{C'(v)} \le -2[/math] - аналогично доказанному ранее, что и требовалось доказать. Итого, получаем, что амортизированное время шага zig-zag не превосходит [math]2(r'(v) - r(v)) \le 3(r'(v) - r(v))[/math]. Поскольку за время выполнения операции splay выполняется не более одного шага типа zig, то суммарное время не будет превосходить [math]3r(t) - 3r(v) + 1[/math], поскольку утроенные ранги промежуточных вершин сокращаются (входят в сумму как с плюсом, так и с минусом).

[math]\triangleleft[/math]

Литература

1. Daniel Sleator, Robert Tarjan "A data structure for dynamic trees"