Splay-дерево

Материал из Algocode wiki
Перейти к: навигация, поиск

Splay-дерево

Двоичное дерево поиска. Быстрый доступ к недавно использовавшимся данным.

Что храним?

Для каждой вершины будем помнить её значение, левого и правого сыновей, а также родителя.

1 struct node {
2   int x;
3   node *left, *right, *parent;
4   node(int _x) {
5     x = _x;
6     left = right = parent = nullptr;
7   }
8   ...
9 };

Функция splay

Вызывается от некоторой вершины v и делает её корнем, осуществляя повороты вокруг рёбер. Затем станет видно, что если вызвать splay от вершины, от которой мы вызывались недавно, то он отработает очень быстро.

Повороты
zig Поворот вокруг ребра вершина-отец. Осуществляется, когда у вершины нет деда. В противном случае осуществляется или zigzag, или zigzig.
Zig.PNG
zigzig Поворот вершина-отец, затем снова вершина-отец. Осуществляется, когда отец и дед находятся по одну сторону от вершины.
Zig-zig.PNG
zigzag Поворот отец-дед, затем вершина-отец. Осуществляется, когда отец и дед находятся по разные стороны от вершины.
Zig-zag.PNG

Реализация splay

 1 static void rotate_left(node* v) {
 2   node* p = v->parent;
 3   node* r = v->right;
 4   if (p) {
 5     if (p->left == v)
 6       p->left = r;
 7     else
 8       p->right = r;
 9   }
10   node* tmp = r->left;
11   r->left = v;
12   v->right = tmp;
13   v->parent = r;
14   r->parent = p;
15   if (v->right)
16     v->right->parent = v;
17 }
18 
19 static void rotate_right(node* v) {
20   // симметрично rotate_left
21 }
22 
23 static void splay(node* v) {
24   while (v->parent) {
25     node* g = v->parent->parent;
26     if (v == v->parent->left) {
27       if (!g) {
28         rotate_right(v->parent);
29       } else {
30         rotate_right(g);
31         rotate_right(v->parent);
32       } else {
33         rotate_right(v->parent);
34         rotate_left(v->parent);
35       }
36     } else {
37       // симметрично
38     }
39   }
40 }

Все остальные функции

Идея состоит в том, что после любой функции мы будем вызывать splay от самой нижней посещенной вершины (если splay не вызывался от какой-нибудь ещё вершины). Понятно, что в таком случае время работы всех операций (асимптотически) будет такое же, как и время работы всех splay'ев (все операции будут выполняться за глубину самой нижней посещенной вершины). Умные люди умеют доказывать, что все splay'и суммарно работают за $O(q * log n)$. Однако иногда splay-дерево вырождается в бамбук, и некоторые операции будут делаются за $O(n)$. Поэтому не стоит делать splay-дерево персистентным.

Insert(x)

Просто спускаемся по дереву и ставим элемент, куда надо. Вызываем от него splay.

Merge(l, r)

Поднимаем в корень левого дерева вершину с наибольшим ключом. Сделаем корень правого дерева её правым ребёнком.

Erase(x)

Ищем элемент. Если он нашёлся, то вызываем от него splay и затем заменяем его на merge его детей. Если он не нашёлся, то поднимем в корень самую нижнюю посещенную вершину.

Split(x)

Найдём вершину с наибольшим ключом, не превосходящим x, поднимем её в корень. Запомним её правого сына. Удалим ребро. Как результат вернем вершину и её бывшего правого сына.

Несколько слов про неявный ключ

Так как это бинарное дерево поиска, его можно написать и по неявному ключу. Тогда в rotate_left, rotate_right, split и merge необходимо дописать вызов функции upd, поддерживающей размеры деревьев.

Если есть массовые операции на отрезках (например, разворот), то помимо обычных push'ей следует вызывать push от деда и отца вершины, когда мы поднимаем вершину к корню.



Автор конспекта: Герман Перов

По всем вопросам пишите в telegram @gmusya