Декартово дерево
Декартово дерево — это структура данных, реализующая двоичное дерево поиска. Стандартный сценарий использования декартового дерева - это реализация следующего функционала:
- Вставка элемента в множество
- Удаление элемента из множества
- Нахождение элемента в множестве
- Нахождение первого элемента, меньшего $x$
- и многое-многое другое
Содержание
Структура дерева
В каждой вершине мы будем хранить два числа — ключ $x$, по которому наша структура будет бинарным деревом поиска, а также приоритет $y$, по которому наше дерево будет кучей. Приоритеты нужно выбирать случайно, на этом будет опираться оценка высоты дерева. Пока что будем считать, что высота дерева $O(\log n)$, но докажем это ниже.
Основные операции
Все операции с декартовым деревом реализуются с помощью двух основных — $split$ и $merge$:
- $split(t,\ x)$ делит декартово дерево $t$ на два — в одном все ключи меньше $x$, все остальные вершины в другом.
- $merge(l,\ r)$ сливает два декартовых дерева в одно при условии, что все ключи в $l$ меньше, чем в $r$.
Реализовать $insert\ x$ можно через
l, r = split(t, x)
l = merge (x, new node(x))
t = merge (l, r)
Аналогичным образом можно выразить и остальные операции.
merge
Делать merge будем так:
- $merge(\empty, t) = t$
- $merge(t, \empty) = t$
- Теперь научимся делать $merge(l, r)$. Посмотрим на $l_y, r_y$. Если $l_y > r_y$, то сделаем $l_r = merge(l_r, r)$. Иначе $r_l = merge(l, r_l)$. Нетрудно видеть, что таким образом мы получим бинарное дерево по $x$ и кучу на максимум по $y$.
split
Делать split будем так:
- $split(\empty, x) = \empty$
- Для непустого дерева сделаем так — посмотрим на значение $x$ в корне и решим, куда должен перейти корень — в левое или правое дерево. Осюда и выразим оба случая
- если $t_x < x$, то сделаем $split(t_r, x)$. Левый результат сделаем правым сыном $t$ и получим два итоговых дерева.
- иначе сделаем $split(t_l, x)$, приклеим правый результат к $t$ слева.
Реализация
У нас будет реализация, которая использует механизм ссылок в C++. Вместо того, чтобы возвращать дерево (или даже пару деревьев) мы будем хранить ссылку на переменную, в которую надо записать возвращаемые значения. Это делает нашу реализацию проще для написания.
1 struct treap {
2 treap *l = nullptr, *r = nullptr;
3 int x;
4 int y;
5 treap(int x): x(x){
6 y = get_random_int(); // your favorite random
7 }
8 };
9
10 treap *root = nullptr;
11
12 void split(treap *t, treap *&l, treap *&r, int x) {
13 if (t == nullptr) {
14 l = nullptr;
15 r = nullptr;
16 return;
17 }
18 if (t->x < x) {
19 split(t->r, t->r, r, x);
20 l = t;
21 }
22 else {
23 split(t->l, l, t->l, x);
24 l = t;
25 }
26 }
27
28 void merge(treap *&t, treap *l, treap *r) {
29 if (l == nullptr) {
30 t = r;
31 return;
32 }
33 if (r == nullptr) {
34 t = l;
35 return;
36 }
37 if (l->y >= r->y) {
38 merge(l->r, l->r, r);
39 t = l;
40 }
41 else {
42 merge(r->l, l, r->l);
43 t = r;
44 }
45 }
Функция в поддереве и массовые операции
Пока что наша структура данных была не сильно полезнее, чем $std::set$. Заметим, что мы можем считать функции в поддереве (например, сумму), которую можно вычислять, опираясь на значения в вершине и ее детях (точно так же, как в дереве отрезков. А также мы можем сделать массовую операцию на декартовом дереве, воспользовавшись техникой отложенных операций.
Неявный ключ
Заметим, что мы практически не пользовались ключами при работе с декартовым деревом. Если точнее, то мы смотрели на него только в $split$, когда решали, в правое или левое дерево должна перейти вершина.
Давайте попробуем сделать такой $split(t, x)$, который вернет два дерева $l, r$ такие, что $size(l) = x$. Для этого нам надо будет считать размеры поддеревьев (см. предыдущий пункт.):
- $split(t, x)$, если $size(t_l) > x$, требует от нас $split(t_l, x)$
- иначе, $split(t, x)$, требует от нас $split(t_r, x - size(t_l) - 1)$.
1 struct treap {
2 treap *l, *r;
3 int sz;
4 int y;
5 };
6
7 int getsz(treap *t) {
8 if (t == nullptr) {
9 return 0;
10 }
11 return t->sz;
12 }
13
14 void upd(treap *t) {
15 if (t == nullptr) {
16 return;
17 }
18 t->sz = getsz(t->l) + getsz(t->r) + 1;
19 }
20
21 void split(treap *t, treap *&l, treap *&r, int x) {
22 if (t == nullptr) {
23 l = nullptr;
24 r = nullptr;
25 return;
26 }
27 if (getsz(t->l) + 1 >= x) {
28 split(t->l, l, t->l, x);
29 r = t;
30 }
31 else {
32 split(t->r, t->r, r, x - getsz(t->l) - 1);
33 l = t;
34 }
35 upd(l);
36 upd(r);
37 }
38
39 void merge(treap *&t, treap *l, treap *r) {
40 if (l == nullptr) {
41 t = r;
42 upd(t);
43 return;
44 }
45 if (r == nullptr) {
46 t = l;
47 upd(t);
48 return;
49 }
50 if (l->y >= r->y) {
51 merge(l->r, l->r, r);
52 t = l;
53 }
54 else {
55 merge(r->l, l, r->l);
56 t = r;
57 }
58 upd(t);
59 }
Время работы
Все операции с декартовым деревом работают за $O(h)$, где $h$ — высота дерева.
Утверждение:
При случайном выборе приоритетов высота дерева $O(\log n)$.
Доказательство:
Матожидание высоты вершины — это матожидание числа ее предков. Вершина $A$ является предком вершины $B$, если $A_y = \max (A_y, (A + 1)_y, \ldots, B_y)$ (что происходит с вероятностью $\frac{1}{|B - A| + 1}$. Матожидание числа предков вершины $v$ — $\sum_{i=1}^{n} \frac{1}{|v - i| + 1} \le \sum_{i=1}^{n} \frac {1}{i} = O(\log n)$
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @KiKoS