Splay-дерево

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

Основной идеей работы дерева является эвристика "Move to Root", перетаскивающая найденную вершину в корень почти после каждой операции. Для p - предка вершины x "Move to Root" совершает повороты вокруг ребра (x, p), пока x не окажется корнем дерева.

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

Splay

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

Zig

Если p - корень дерева с сыном x, то совершаем один поворот вокруг ребра (x, p), делая x корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина x была нечетной.

Zig-Zig

Если p - не корень дерева, а x и p - оба левые или оба правые дети, то делаем поворот ребра (p, g), где g отец p, а затем поворот ребра (x, p).

Zig-Zag

Если p - не корень дерева и x - левый ребенок, а p - правый, или наоборот, то делаем поворот вокруг ребра (x, p), а затем поворот нового ребра (x, g), где g - бывший родитель p.

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

Find(key)

Эта операция выполняется как для обычного бинарного дерева, только после нее запускается операция Splay.

Merge(Tree1, Tree2)

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

Split(key, Tree)

Запускаем Splay от элемента key и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем key.

Add(key, Tree)

Запускаем Split(key, Tree), который нам возвращает деревья Tree_1 и Tree_2, их подвешиваем к key как левое и правое поддеревья соответственно.

Remove(key, Tree)

Запускаем Splay от key элемента и возвращаем 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]

Литература

• Splay tree - Википедия
• Sleator, Daniel D.; Tarjan, Robert E."Self-Adjusting Binary Search Trees"