Декартово дерево
Редактирование данной статьи ещё не завершено.
Общие сведения
Вычислительная сложность большинства операций с двоичными деревьями поиска пропорциональна высоте дерева. Высота дерева определяется порядком добавления и удаления его элементов. Дерево, содержащее N элементов, может иметь высоту от ⌈log2N⌉ до N.
Пусть каждый узел двоичного дерева поиска имеет, кроме ключа, дополнительное значение, именуемое приоритетом, и установлено следующее дополнительное ограничение: элементы дерева по своим приоритетам формируют пирамиду, то есть приоритет каждого из узлов не меньше приоритетов его потомков (случай максимальной пирамиды). Тогда, вне зависимости от порядка операций с получившимся деревом, его форма задана однозначно.
Убедиться в справедливости данного утверждения можно следующим образом. Корнем дерева является элемент с наибольшим приоритетом. В левом поддереве располагаются элементы, ключи которых не превышают ключа корня, в правом поддереве — остальные элементы (дерево продолжает оставаться деревом поиска). Рекурсивно рассматривая левое и правое поддеревья (корнями которых также являются их элементы с максимальными приоритетами, и так далее), приходим к выводу, что положение каждого элемента дерева задано однозначно, зависит от пары (ключ — приоритет) и не зависит от порядка добавления элементов в дерево.
- Примеры декартовых деревьев
- Treap example 1.jpg
- Treap example 2.jpg
Можно показать, что доля двоичных деревьев поиска из N элементов, высота которых не превышает ⌈4log2N⌉, стремится к 100%. Этот факт позволяет применить идею рандомизированного алгоритма: если приоритеты узлов назначаются при добавлении случайным образом, то вероятность того, что получившееся дерево будет иметь высоту, превышающую ⌈4log2N⌉, становится пренебрежимо малой. Таким образом, дерево поиска со случайными приоритетами, элементы которого формируют пирамиду по приоритетам, позволяет выполнять основные операции со сложностью O(logN).
Описанная структура данных называется декартовым деревом (дерамидой, англ. cartesian tree, treap). Если пары (ключ — приоритет) рассматривать как координаты узла на декартовой плоскости, то любое нарисованное таким образом декартово дерево будет планарным (не будет иметь рёберных пересечений).
Демонстрация работы
Визуализатор древовидных структур, вкладка «Treap».
Реализация базовых операций
Прежде всего определим тип элемента дерамиды TreapNode. Его полями являются ключ, приоритет и хранимое значение, а также указатели на левого и правого потомков.
struct TreapNode {
int k, p, v;
TreapNode *l, *r;
TreapNode(int key, int value) {
k = key;
v = value;
p = (double)rand() / RAND_MAX * 100000;
l = r = NULL;
}
};
Слияние декартовых деревьев (merge)
Пусть даны две дерамиды A (с корнем a) и B (с корнем b), причём ключи элементов A меньше ключей элементов B. Требуется сформировать новую дерамиду T из элементов A и B и вернуть указатель на её корень.
TreapNode *merge(TreapNode *a, TreapNode *b) {
if (!a || !b)
return a ? a : b;
if (a->p > b->p) {
a->r = merge(a->r, b);
return a;
} else {
b->l = merge(a, b->l);
return b;
}
}
Корнем T будет тот элемент A или B, приоритет которого является максимальным. Нетрудно заметить, что таковым элементом может быть либо a, либо b. Пусть (a->p > b->p), тогда a является корнем результата. Все добавляемые к A элементы B имеют ключи, большие a->k, поэтому они все будут помещены в поддерево a->r. Таким образом, мы перешли от задачи объединения A и B к задаче объединения a->r и B; налицо рекурсивный характер реализации слияния (симметричный случай рассматривается аналогично). Базой рекурсии является случай, когда хотя бы одна из объединяемых дерамид является пустой.
Разрезание декартового дерева (split)
Пусть дана дерамида T (с корнем t) и некоторое число k. Требуется составить две дерамиды: A, содержащую те элементы T, ключи которых не превышают k, и B, содержащую все остальные элементы T. Функция должна возвращать два значения; в рассмотренной реализации они передаются через параметры, а возвращаемым типом является void.
void split(TreapNode *t, int k, TreapNode *&a, TreapNode *&b) {
if (!t)
a = b = NULL;
else if (t->k <= k) {
split(t->r, k, t->r, b);
a = t;
} else {
split(t->l, k, a, t->l);
b = t;
}
}
Если (t->k <= k), то t станет элементом A, иначе — элементом B. Пусть t становится частью A (нетрудно заметить, что t станет корнем A), тогда все элементы поддерева t->l также становятся частью A, так как их ключи меньше t->k, а следовательно, меньше k. Ситуация с поддеревом t->r сложнее: оно может содержать как элементы, ключи которых не превышают k, так и элементы, ключи которых превышают k. Поступим следующим образом: рекурсивно разрежем t->r по k, при этом получатся две дерамиды A' и B'. Дерамиду A' нужно оставить на месте t->r, тогда T будет содержать только элементы, ключи которых не превышают k. B' содержит только элементы с ключами, большими k. Таким образом, результатами операции разрезания являются T и B'. Симметричный случай рассматривается аналогично. Можно видеть, что операция разрезания также реализуется рекурсивно; базой рекурсии является случай, когда T пуста.
Реализация операций двоичного дерева поиска
Как будет показано ниже, на базе дерамиды очень просто реализуются все основные операции двоичного дерева поиска. При этом, приведённое ранее утверждение о том, что высота дерамиды со случайными приоритетами имеет порядок O(logN), позволяет сделать вывод, что асимптотика основных операций лвоичного дерева поиска также не превышает O(logN). Из этого следует, что декартовы деревья можно рассматривать как балансирующиеся двоичные деревья поиска, имеющие достаточно простую реализацию.
Будем считать, что указатель TreapNode *t ссылается на корень дерамиды.
Поиск элемента
С учётом того, что декартово дерево по ключам продолжает оставаться двоичным деревом поиска, операция отыскания элемента с заданным ключом абсолютно не отличается от таковой для обычного двоичного дерева поиска.
Показанная ниже операция возвращает указатель на элемент дерева с указанным ключом. Если таких элементов нет, то возвращается значение NULL.
TreapNode *find(int key) {
TreapNode *n = t;
while (n != NULL && n->k != key)
n = (key < n->k ? n->l : n->r);
return n;
}
Вставка элемента
Пусть в декартово дерево T нужно добавить новый элемент с ключом key и значением value. Этот элемент можно рассмотреть как полноценную дерамиду Tn (имеющую только один узел). Следовательно, можно произвести слияние исходной дерамиды с добавляемой. Однако для этого нужно обеспечить выполнение предварительного условия (все ключи в первой дерамиде должны быть меньше любого из ключей во второй дерамиде). Поэтому сначала разрежем T на две части: T1, содержащую ключи, меньшие key, и T2, содержащую все остальные ключи. Теперь можно произвести два слияния, после чего элемент будет успешно добавлен в декартово дерево T.
void insert(int key, int value) {
TreapNode *tn = new TreapNode(key, value), *t1, *t2;
split(t, key - 1, t1, t2);
t = merge(t1, tn);
t = merge(t, t2);
}
Удаление элемента
Пусть требуется исключить из дерамиды T все элементы, ключи которых равны key. Разрежем T на дерамиды T1 и T2 по ключу (key - 1). Тогда все элементы T1 имеют ключи, меньшие key. Разрежем T2 по ключу key: правая получившаяся часть (T3) содержит элементы, ключи которых больше key, а в T2 останутся только элементы с ключами, равными key. Таким образом, после объединения T1 и T3 мы получим декартово дерево, не содержащее элементов с ключами key.
Если требуется освободить память, занимаемую исключаемыми элементами, то можно воспользоваться простой рекурсивной процедурой, приведённой справа.
void remove(int key) {
TreapNode *t1, *t2, *t3;
split(t, key - 1, t1, t2);
split(t2, key, t2, t3);
t = merge(t1, t3);
dispose(t2);
}
|
void dispose(TreapNode *n) {
if (n == NULL)
return;
dispose(n->l);
dispose(n->r);
delete n;
}
|
Реализация групповых запросов
Декартовы деревья достаточно просто модифицируются для работы с групповыми запросами на элементах: определению суммы, произведения, подсчёту количества, выявлению максимума и т. п. В качестве примера рассмотрим реализацию запросов суммы и минимума в дерамиде.
Запросы на всём дереве
Пусть требуется вычислять сумму значений всех элементов, хранящихся в дерамиде, а также определять количество этих значений.
Модифицируем структуру TreapNode: добавим поля cnt и sum, которые будут хранить соответственно количество и сумму значений элементов, расположенных в поддереве, корнем которого является текущий элемент. Очевидно, что в конструкторе TreapNode поле sum следует проинициализировать значением элемента, а поле cnt — единицей.
Также добавим процедуру update(), которая будет пересчитывать значения sum и cnt у текущего элемента в предположении, что у его потомков они посчитаны правильно.
struct TreapNode {
int k, p, v;
int sum, cnt;
TreapNode *l, *r;
TreapNode(int key, int value) {
k = key;
v = value;
p = (double)rand() / RAND_MAX * 100000;
l = r = NULL;
sum = value;
cnt = 1;
}
};
|
int getSum(TreapNode *n) {
return n != NULL ? n->sum : 0;
}
int getCnt(TreapNode *n) {
return n != NULL ? n->cnt : 0;
}
void update(TreapNode *n) {
if (n == NULL) return;
n->sum = v + getSum(n->l) + getSum(n->r);
n->cnt = 1 + getCnt(n->l) + getCnt(n->r);
}
|
Далее необходимо модифицировать операции merge() и split() таким образом, чтобы возвращаемые ими результаты имели корректные значения sum и cnt. Для этого нужно вставить вызовы функции update() для каждого возвращаемого значения. Обе процедуры являются рекурсивными, и если внутренние вызовы правильно пересчитывают sum и cnt, то и текущий вызов обновит их нужным образом. Достаточно легко показать, что базовые случаи (для merge() — когда a или b равно NULL, для split() — когда t равно NULL) правильно обрабатываются операцией update(), из чего по индукции следует общая корректность обновления.
TreapNode *merge(TreapNode *a, TreapNode *b) {
if (!a || !b)
return a ? a : b;
if (a->p > b->p) {
a->r = merge(a->r, b);
update(a);
return a;
} else {
b->l = merge(a, b->l);
update(b);
return b;
}
}
|
void split(TreapNode *t, int k,
TreapNode *&a, TreapNode *&b) {
if (!t)
a = b = NULL;
else if (t->k <= k) {
split(t->r, k, t->r, b);
a = t;
} else {
split(t->l, k, a, t->l);
b = t;
}
update(a); update(b);
}
|
Теперь, если нужно получить сумму значений или количество элементов в дерамиде, достаточно проверить соответствующее поле у её корня.
Запросы на отрезках
Пусть теперь требуется определять сумму или количество только для элементов, ключи которых принадлежат некоторому отрезку [k1; k2]. Выделить в дерамиде составляющую, содержащую все элементы с указанными ключами, можно с помощью двух разрезаний (как при удалении элемента), а определение интересующего значения для всей дерамиды рассмотрено в редыдущем пункте.
Руководствуясь этими рассуждениями, можно привести простую реализацию запроса на подотрезках дерамиды. Следует помнить, что после определения ответа исходную дерамиду требуется восстановить («собрать» обратно).
int sum(int k1, int k2) {
TreapNode *t1, *t2, *t3;
split(t, k1 - 1, t1, t2);
split(t2, k2, t2, t3);
int s = getSum(t2);
t1 = merge(t1, t2);
t = merge(t1, t3);
return s;
}
Задачи, решаемые с помощью декартовых деревьев
Одним из основных преимуществ декартовых деревьев является сравнительная простота реализации, что нередко оказывается важным в условиях соревнования. Как можно видеть, дерамиды имеют достаточно широкий спектр применения:
- Задачи, в которых требуется достаточно сбалансированное дерево поиска (например, эффективная реализация множеств или словарей);
- Широкий класс задач с запросами на диапазонах (RSQ, RMQ и др.). Если данные задачи предполагают также групповое обновление элементов, то декартовы деревья являются одной из немногих структур данных, позволяющих эффективно их решать (конкуренцию им составляют деревья отрезков, однако они проигрывают декартовым деревьям по сложности реализации);
- Поиск порядковых статистик (определение k-го по величине элемента) за O(logN). В этом случае нужно поддерживать количества элементов во всех поддеревьях, и далее по этой информации определять, в каком поддереве будет располагаться нужный элемент;
- Решение обратной задачи (определение номера элемента в отсортированной последовательности) за O(logN). Требуется разрезать дерамиду по заданному ключу и определить количество элементов в левой части;
- Декартово дерево служит основой для ещё более мощной структуры данных, именуемой декартовым деревом по неявному ключу, которую можно рассматривать как массив, позволяющий производить большое количество различных операций с логарифмическим временем выполнения.