Декартово дерево (treap, дерамида)¶
Декартово дерево - это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: treap (tree+heap) и дерамида (дерево+пирамида).
Более строго, это структура данных, которая хранит пары \((X,Y)\) в виде бинарного дерева таким образом, что она является бинарным деревом поиска по \(x\) и бинарной пирамидой по \(y\). Предполагая, что все \(X\) и все \(Y\) являются различными, получаем, что если некоторый элемент дерева содержит \((X_0,Y_0)\), то у всех элементов в левом поддереве \(X < X_0\), у всех элементов в правом поддереве \(X > X_0\), а также и в левом, и в правом поддереве имеем: \(Y < Y_0\).
Дерамиды были предложены Сиделем (Siedel) и Арагон (Aragon) в 1989 г.
Преимущества такой организации данных¶
В том применении, которое мы рассматриваем (мы будем рассматривать дерамиды, поскольку декартово дерево - это фактически более общая структура данных), X’ы являются ключами (и одновременно значениями, хранящимися в структуре данных), а Y’и - называются приоритетами. Если бы приоритетов не было, то было бы обычное бинарное дерево поиска по X, и заданному набору X’ов могло бы соответствовать много деревьев, некоторые из которых являются вырожденными (например, в виде цепочки), а потому чрезвычайно медленными (основные операции выполнялись бы за \(O(n)\)).
В то же время, приоритеты позволяют однозначно указать дерево, которое будет построено (разумеется, не зависящее от порядка добавления элементов) (это доказывается соответствующей теоремой). Теперь очевидно, что если выбирать приоритеты случайно, то этим мы добьёмся построения невырожденных деревьев в среднем случае, что обеспечит асимптотику \(O(log(n))\) в среднем. Отсюда и понятно ещё одно название этой структуры данных - рандомизированное бинарное дерево поиска.
Операции¶
Итак, treap предоставляет следующие операции:
- \(Insert (X, Y)\) - за \(O(log(n))\) в среднем. Выполняет добавление в дерево нового элемента. Возможен вариант, при котором значение приоритета \(Y\) не передаётся функции, а выбирается случайно (правда, нужно учесть, что оно не должно совпадать ни с каким другим \(Y\) в дереве).
- \(Search(X)\) - за \(O(log(n))\) в среднем. Ищет элемент с указанным значением ключа \(X\). Реализуется абсолютно так же, как и для обычного бинарного дерева поиска.
- \(Erase(X)\) - за \(O(log(n))\) в среднем. Ищет элемент и удаляет его из дерева.
- \(Build (X1, ..., XN)\) - за \(O(N)\) Строит дерево из списка значений.
- \(Union (T1, T2)\) - за \(O(m log(n / m))\) в среднем. Объединяет два дерева, в предположении, что все элементы различны (впрочем, эту операцию можно реализовать с той же асимптотикой, если при объединении нужно удалять повторяющиеся элементы).
- \(Intersect(T1, T2)\) - за \(O(m log (n / m))\) в среднем находит пересечение двух деревьев (т.е. их общие элементы).
Описание реализации¶
С точки зрения реализации, каждый элемент содержит в себе X, Y и указатели на левого L и правого R сына.
Для реализации операций понадобится реализовать две вспомогательные операции: Split и Merge.
\(Split(T, X)\) - разделяет дерево \(T\) на два дерева \(L\) и \(R\) (которые являются возвращаемым значением) таким образом, что \(L\) содержит все элементы, меньшие по ключу \(X\), а \(R\) содержит все элементы, большие \(X\). Эта операция выполняется за \(O(log(n))\). Реализация её довольно проста - очевидная рекурсия.
\(Merge(T1, T2)\) - объединяет два поддерева \(T1\) и \(T2\), и возвращает это новое дерево. Эта операция также реализуется за \(O(log(N))\). Она работает в предположении, что \(T1\) и \(T2\) обладают соответствующим порядком (все значения \(X\) в первом меньше значений \(X\) во втором). Таким образом, нам нужно объединить их так, чтобы не нарушить порядок по приоритетам \(Y\). Для этого просто выбираем в качестве корня то дерево, у которого \(Y\) в корне больше, и рекурсивно вызываем себя от другого дерева и соответствующего сына выбранного дерева.
Теперь очевидна реализация \(Insert (X, Y)\). Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по \(X\)), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше \(Y\). Мы нашли позицию, куда будем вставлять наш элемент. Теперь вызываем \(Split (X)\) от найденного элемента (от элемента вместе со всем его поддеревом), и возвращаемые ею \(L\) и \(R\) записываем в качестве левого и правого сына добавляемого элемента.
Также понятна и реализация \(Erase(X)\). Спускаемся по дереву (как в обычном бинарном дереве поиска по \(X\)), ища удаляемый элемент. Найдя элемент, мы просто вызываем \(Merge\) от его левого и правого сыновей, и возвращаемое ею значение ставим на место удаляемого элемента.
Операцию \(Build\) реализуем за:
- \(O(nlog(n))\) просто с помощью последовательных вызовов \(Insert\).
- \(O(n)\) с помощью стека TODO (task A pcms)
Наконец, операция Union (T1, T2). Теоретически её асимптотика O (M log (N/M)), однако на практике она работает очень хорошо, вероятно, с весьма малой скрытой константой. Пусть, не теряя общности, T1->Y > T2->Y, т.е. корень T1 будет корнем результата. Чтобы получить результат, нам нужно объединить деревья T1->L, T1->R и T2 в два таких дерева, чтобы их можно было сделать сыновьями T1. Для этого вызовем Split (T2, T1->X), тем самым мы разобъём T2 на две половинки L и R, которые затем рекурсивно объединим с сыновьями T1: Union (T1->L, L) и Union (T1->R, R), тем самым мы построим левое и правое поддеревья результата.
Реализация¶
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node {
ll x, y, n;
Node *L, *R;
Node(ll x) : x(x), y(rand()), L(0), R(0) {};
Node(ll x, ll y) : x(x), y(y), L(0), R(0) {};
Node(ll x, ll y, ll n) : x(x), y(y), n(n), L(0), R(0) {};
};
Node *merge(Node *a, Node *b) {
if (!a) return b;
if (!b) return a;
if (a->y < b->y) {
a->R = merge(a->R, b);
return a;
} else {
b->L = merge(a, b->L);
return b;
}
}
pair<Node *, Node *> split(Node *t, ll x) {
if (!t) return {nullptr, nullptr};
if (t->x < x) {
auto r = split(t->R, x);
t->R = r.first;
return {t, r.second};
} else {
auto l = split(t->L, x);
t->L = l.second;
return {l.first, t};
};
}
Node *add(Node *t, ll x) {
auto tmp = split(t, x);
return merge(tmp.first,
merge(new Node(x), tmp.second));
}
Node *erase(Node *t, ll x) {
auto tmp1 = split(t, x);
auto tmp2 = split(tmp1.second, x + 1);
return merge(tmp1.first, tmp2.second);
}
bool find(Node *t, ll x) {
auto tmp1 = split(t, x);
auto tmp2 = split(tmp1.second, x + 1);
bool ans = tmp2.first != nullptr;
t = merge(tmp1.first, merge(tmp2.first, tmp2.second));
return ans;
}
ll next(Node *root, int x) {
pair <Node*, Node*> t = split(root, x + 1);
Node *cur = t.second;
if (cur == nullptr){
return x;
}
while (cur->L != nullptr){
cur = cur->L;
}
root = merge(t.first, t.second);
return cur->x;
}
ll prev(Node *root, int x) {
pair <Node*, Node*> t = split(root, x);
Node *cur = t.first;
if (cur == nullptr){
return x;
}
while (cur -> R != nullptr){
cur = cur->R;
}
root = merge(t.first, t.second);
return cur->x;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
srand(time(0));
string s;
ll x;
Node *t = nullptr;
while (cin >> s) {
cin >> x;
if (s == "insert") {
if (!find(t, x))
t = add(t, x);
} else if (s == "exists") {
//find(t, x);
if (find(t, x)) {
cout << "true\n";
} else {
cout << "false\n";
}
} else if (s == "next") {
auto q = next(t, x);
if (q != x) {
cout << q << endl;
} else {
cout << "none" << endl;
}
} else if (s == "delete"){
if (find(t, x))
t = erase(t, x);
} else if (s == "prev"){
auto q = prev(t, x);
if (q != x){
cout << q << endl;
} else {
cout << "none\n";
}
}
}
return 0;
}