Splay-дерево
Содержание
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 .
|
|
zigzig
|
Поворот вершина-отец, затем снова вершина-отец. Осуществляется, когда отец и дед находятся по одну сторону от вершины. | |
zigzag
|
Поворот отец-дед, затем вершина-отец. Осуществляется, когда отец и дед находятся по разные стороны от вершины. |
Реализация 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