\Section{Декартово дерево}{12 февраля}{Жидков Николай}


\Subsection{Декартово дерево (cartesian tree)}

В обычном дереве поиска каждой вершине соответствует пара из ключа и информации.
Теперь в каждой вершине так же будет хранится ее приоритет (поле $y$).
Декартово дерево - это дерево поиска, в котором доплнительно выполнен следующий инвариант: приоритет родителя меньше (или меньше или равен, если приоритеы могут совпадать), чем у его детей.
Другими словами, $v$-->$y$ меньше $v$-->$l$-->$y$ и $v$-->$r$-->$y$.
Получается, что cartesian tree -- это дерево поиска по ключам($x$) и куча по приоритетам($y$).
Так как каждая вершина представляет собой пару $(x, y)$, то удобно рисовать декартово дерево на плоскости.

\Subsection{Декартово дерево (treap)}

Treap -- это cartesian tree, только все приоритеты выбираются случайным образом.
Другими словами, это обычное дерево поиска, только каждой вершине сопоставлен случайный приоритет, который у сыновей должен быть больше, чем у родителей.
Так же будем считать, что все приоритеты различны (на практике обычно у нас порядка $10^5$ вершин, а приоритеты выбираются из промежутка $[1..10^9]$, поэтому вероятность совпадения крайне мала).

\begin{Lm}
Декартово дерево единственно.
\end{Lm}

\begin{proof}
Покажем это рекурсивно.
Понятно, что вершина с самым маленьким приоритетом $u$ должна быть корнем (так как приоритеты разные, такая вершина определяется однозначно).
Теперь все вершины разделились на 2 группы - те, у которых ключ меньше $u$-->$x$, и те, у которых ключ больше или равен, чем $u$-->$x$.
При этом в каждой группе все приоритеты меньше, чем у $u$, поэтому можно просто рекурсивно построить деревья для этих групп, а потом сделать их корни левым и правым сыном $u$.
\end{proof}

\begin{Lm}
Декартово дерево -- случайное дерево.
\end{Lm}

\begin{proof}
Корнем дерева может быть любая вершина с одинаковой вероятностью (вероятность того, что ее приоритет больше остальных).
Заметим, что в определении случайного дерева корень тоже выбирался равновероятно.
Далее построение дерева слева и справа от корня идет независимо, при этом, например, слева корнем снова станет случайная вершина из оставшихся, так же, как и при построении случайного дерева.
В общем, видно, что процедура построения декартова дерева идентична построению случайного дерева, если сказать, что мы рассматриваем вершины в порядке увеличения приоритетов. 
Тогда каждая перестановка вершин равновероятна, и мы получаем случайное дерево.
\end{proof}

Пока что мы только показали, что если строить декартово дерево по алгоритму из доказательства первой леммы, то мы получим случайное дерево, а значит, его средняя глубина будет не больше $2\ln n$, а максимальная глубина не превосходит $4 \ln n$.
Так же можно заметить, что время построения treap оценивается рекурсивным соотношением $T(n)=T(x)+T(n-x-1)+n$, которое полностью идентично тому, что мы получали при оценке времени работы $qsort$.
Поэтому, построение декартова дерева работает $O(n \ln n)$.

\Subsection{О равных ключах}
В общем случае считается, что в cartesian tree в левом поддереве лежат вершины с меньшим ключом, а в правом - с большим или равным.
На практике в зависимости от задачи можно хранить пары из ключа и времени его добавления, можно в вершинке хранить вектор всех вершин с таким ключом, можно позволить существовать нескольким вершинам с разным ключом.
Я буду придерживаться последнего варианта.

\Subsection{Split}
Функция, принимающая на вход дерево $T$ и ключ $x$.
Возвращает пару деревьев $l, r$ такую, что множество вершин из $T$ - это множество вершин из объединения $l$ и $r$, при этом ключи вершин из $l$ меньше х, а ключи вершин из $r$ больше или равны $x$.
Если нарисовать дерево на плоскости, то мы проводим вертикальную черту и делим дерево на две части, лежащие по разные стороны от этой черты.
Алгорим рекурсивный. Пусть мы стоим в вершине $v$. 
Тогда, если ее ключ сейчас меньше $x$, то она и ее левое поддерево останутся слева от $x$ и не изменятся.
Поэтому мы вызываемся рекурсивно от правого сына и получаем его разбиение на $l_1, r_1$ (то есть, мы разделили правого сына $v$ на две части, одна из которых меньше $x$ и останется сыном $v$, а другая часть лежит справа от $x$, и поэтому она уже не будет связана с $v$). 
Теперь нужно в правого сына $v$ положить $l_1$ и вернуть наверх пару из $v$ и $r_1$.
Случай, когда $v$ справа от $x$, разбирается так же.
\begin{code}
pair<node*, node*> split(node *v, int x) {
	if (v == NULL)
		return make_pair(NULL, NULL);
	if (v->x < x) {
		l1, r1 = split(v->r, x);
		v->r = l1
		return make_pair(v, r1);
	} else {
		l1, r1 = split(v->l, x);
		v->l = r1;
		return make_pair(l1, v);
	}
}
\end{code}

\Subsection{Merge}
Функция, обратная split.
Принимает на вход два дерева, между которыми можно провести черту (то есть все ключи одного меньше всех ключей другого) и объединяет их в одно.
Условие про ключи важно, нельзя склеивать два дерева, у которых непонятно как соотносятся ключи.
Алгоритм также рекурисвный.
Пусть мы склеиваем вершины $l$ и $r$.
Понятно, что вершина с меньшим приоритетом станет корнем, пусть, например, $r$.
Тогда ее правый сын не поменяется, а левый сын получится склеиванием $l$ и предыдущего левого сына $r$-->$l$.
Случай, когда приоритет $l$ меньше, разбирается так же.
\begin{code}
node* merge(node *l, node *r) {
	if (l == NULL)
		return r;
	if (r == NULL)
		return l;
	if (l->y > r->y) {
		r->l = merge(l, r->l);
		return r;
	} else {
		l->r = merge(l->r, r);
		return l;
	}
}
\end{code}

\Subsection{Медленные Add и Delete}
Все операции с декартовым деревом обычно выражаются через split, merge и спуск по дереву.
Например, чтобы вставить вершину с ключом $x$, достаточно сначала разрезать дерево по $x$, получить, что новая вершина лежит между двумя кусками дерева, после чего просто склеить сначала левый кусок с новой вершиной, потом получившуюся часть с правым куском.
\begin{code}
node* add(node *T, node *v) {
	l, r = split(T, v->x);
	T = merge(l, v);
	T = merge(T, r);
	return T;
}
\end{code}
Delete выражается аналогично. 
Разрезаем дерево по $x$, потом по $x+1$.
Дерево теперь имеет вид левый кусок, все вершины с ключом $x$, правый кусок.
Далее нужно склеить правый и левые куски, игнорируя вершины между ними.
Здесь важно понимать, что при таком способе удаляться все вершины с ключом $x$.
Если надо удалить только одну, то можно из дерева, в котором все вершины имеют ключ $x$, удалить корень, а оставшиеся части вновь склеить вместе с левым и правым куском.
\begin{code}
node* delete(node*T, int x) {
	l, r = split(T, x);
	l1, r1 = split(r, x + 1);
	return merge(l, l1->l, l1->r, r1); 
}
\end{code}
Это версия с удалением одной, если надо удалить все, можно вернуть $merge(l, r1)$.

Полученные оперции работают от $3$ до $5$ вызовов split/merge, поэтому они не очень быстрые.

\Subsection{Быстрые Add и Delete}
Можно реализовать Add за один split, а Delete за один merge.
Идеи одинаковые, рассмотрим, например, Add.
Если бы у добавляемой вершины был самый маленький приоритет, было бы достаточно разделить дерево одним splitом на две части и подвесить их к новой вершине.
Поэтому общий алгоритм такой: пока приоритеты вершин маленькие, спускаемся вниз.
Как только дошли до того, что у сыновей все приоритеты большие, делим это поддерево одним splitoм и подвешиваем к новой вершине.
\begin{code}
node* add(node *T, node *v) {
	if (v->y < T->y) {
		v->l, v->r = split(T, v->x);
		return v;
	}
	if (v->x < T->x)
		return add(T->l, v);
	else
		return add(T->r, v);
}
\end{code}
Как видно, такой Add работает уже за один $split$.

Операция Delete похожа, достаточно спуститься до удаляемой вершины, сделать merge ее детей и вернуть наверх.

\Subsection{Неявный ключ}
Идея точно такая же, как и в AVL-дереве.
В каждой вершине храним ее размер.
Тогда при поиске $k$-ой вершины смотрим на размер левой компоненты и спускаемся либо налево, либо направо.
Так же надо добавить функцию $recalc(v)$, которая пересчитывает размер поддерева, как только у вершины поменялись дети.
Соответственно, ее надо добавить после всех операций вида $v$-->$l$=$u$.
Легко заметить, что для замены явного ключа на неявный достаточно добавить recalc в нужные места и заменить условие на спуск в split.

\Subsection{Про Add для вещественных чисел}
Заметим, что если ключи вещественные, то для вставки надо писать 2 разных $split$ - один отрезает поддеревья с условиями $(\leqslant x, >x)$, другой
$(<x, \geqslant x)$. Чтобы не писать код дважды, можно сделать дерево по неявному ключу и вместо второго split просто откусывать один элемент.

\Subsection{Приоритеты не нужны}
На самом деле, можно не хранить приоритеты, а в те места, где мы выбираем, какую из двух вершин делать корнем (например, в merge) выбирать левую с вероятностью $\frac{l.size}{l.size+r.size}$.
Утверждается, что от этого асимптотика не изменится (без доказательства).
Такое дерево называется RBST (Randomized Balanced Search Tree).

\Subsection{Время работы}
Мы доказали, что при построении декартова дерева оно получается случайным, и потому его глубина логарифмическая.
Доказательство того, что дерево остается случайным после всех операций split/merge, требует некоторых выкладок, которых мы не делали.
