Декартово дерево

Декартово дерево — это структура данных, реализующая двоичное дерево поиска. Стандартный сценарий использования декартового дерева - это реализация следующего функционала:

• Вставка элемента в множество
• Удаление элемента из множества
• Нахождение элемента в множестве
• Нахождение первого элемента, меньшего $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)$.