Декартово дерево — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (treap = tree + heap, дерамида = дерево + пирамида), была предложена Сиделем и Арагоном в 1996 г.
Дерамида -- это бинарное дерево, в узлах которого хранятся пары `(x,y)`,
где `x` — это ключ, а `y` — это приоритет. Оно является бинарным деревом поиска по `x` и пирамидой по `y`.
Предполагая, что все `x` и все `y` являются различными, получаем, что если
некоторый элемент дерева содержит `(x_0,y_0)`, то у всех
элементов в левом поддереве `x<x_0`, у всех элементов в правом поддереве `x>x_0`, а
также и в левом, и в правом поддереве имеем: `y<y_0`.
--
Почему дерево называется декартовым? Попробуем его нарисовать.
Возьмем какой-нибудь набор пар «ключ-приоритет» и расставим на координатной сетке соответствующие точки `(x, y)`.
А потом соединим соответствующие вершины линиями, образуя дерево.
Таким образом, декартово дерево отлично укладывается на плоскости благодаря своим ограничениям,
а два его основных параметра — ключ и приоритет — в некотором смысле, координаты.
--

--
Если бы приоритетов `y` не было, то это было бы обычное бинарное дерево поиска по `x`,
и в зависимости от порядка добавления значений можно построить разные деревьев,
в том числе вырожденные (в виде цепочки), в которых поиск выполнялся бы за `O(N)`.
После добавления приоритетов из данных пар (x,y) можно построить единственное дерево,
вне зависимости от порядка поступления ключей.
Если в качестве приоритета `y` будем использовать случайное число, тогда полученное декартово дерево с очень высокой
вероятностью будет иметь высоту, не превосходящую `4*log_2 N`.
И хоть оно не является сбалансированным (даже по сравнению с красно-черным деревом, в котором высота гарантированно не превышает `2*log_2 N`),
математическое ожидание времени поиска ключа в таком дереве равно `O(log_2 N)`.
--
Декартово дерево имеет следующие преимущества:
* Проще реализуется по сравнению с настоящими самобалансирующимися деревьями.
* Хорошо ведёт себя «в среднем», если ключи `y` раздать случайно.
* Типичная для сортирующего дерева операция «разделить по ключу на „меньше `k`“ и „не меньше `k`“» выполняется тривиально, а на красно-чёрных деревьях придётся восстанавливать балансировку и окраску узлов.
Операция *разрезать* исходное дерево `T` по ключу `k` возвращает пару деревьев `(T_1,T_2)`, что в дереве `T_1` ключи меньше `k`, а в дереве `T_2`
все остальные.

--
```c++
private:
pair<node*, node*> split(node* t, function<bool(node*)> cond /* условие разделения */) {
if (!t) return {nullptr,nullptr};
if (cond(t)) {
auto [t1,t2]=split(t->right,cond);
t->right=t1;
return {t,t2};
} else {
auto [t1,t2]=split(t->left,cond);
t->left=t2;
return {t1,t};
}
}
```
--
Операция *слить* соединяет пару деревьев `(T_1,T_2)` в одно.
1. Разделим (split) дерево по ключу `x` на дерево `L`, с ключами меньше `x`, и дерево `R`, с большими `x`.
2. Создадим из данного ключа дерево `M` из единственной вершины `(x, y)`, где `y` — только что сгенерированный случайный приоритет.
3. Объединим (merge) по очереди `L` с `M`, то что получилось — с `R`.
1. Разделим сначала дерево по ключу `x`. Все элементы, меньшие `x`, отправились в левый результат, значит, искомый элемент — в правом.
2. Разделим правый результат так, чтобы в новый правый результат отправились все элементы с ключами, большими `x`, а в «средний» (левый от правого) — все меньшие либо равные `x`. Но поскольку строго меньшие после первого шага все были отсеяны, то среднее дерево и есть искомый элемент.
3. Теперь просто объединим снова левое дерево с правым, без среднего, и дерамида осталась без ключей `x`.