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

Материал из Algocode wiki
Версия от 21:27, 8 мая 2020; Rationalex (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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