Декартово дерево
Декартово дерево — это структура данных, реализующая двоичное дерево поиска. Стандартный сценарий использования декартового дерева - это реализация следующего функционала:
- Вставка элемента в множество
- Удаление элемента из множества
- Нахождение элемента в множестве
- Нахождение первого элемента, меньшего $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 }