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

Общие сведения

Файл:Treap trees height comparison.jpg

Различные деревья поиска, созданные из одних и тех же элементов

Вычислительная сложность большинства операций с двоичными деревьями поиска пропорциональна высоте дерева. Высота дерева определяется порядком добавления и удаления его элементов. Дерево, содержащее N элементов, может иметь высоту от ⌈log₂N⌉ до N.

Пусть каждый узел двоичного дерева поиска имеет, кроме ключа, дополнительное значение, именуемое приоритетом, и установлено следующее дополнительное ограничение: элементы дерева по своим приоритетам формируют пирамиду, то есть приоритет каждого из узлов не меньше приоритетов его потомков (случай максимальной пирамиды). Тогда, вне зависимости от порядка операций с получившимся деревом, его форма задана однозначно.

Убедиться в справедливости данного утверждения можно следующим образом. Корнем дерева является элемент с наибольшим приоритетом. В левом поддереве располагаются элементы, ключи которых не превышают ключа корня, в правом поддереве — остальные элементы (дерево продолжает оставаться деревом поиска). Рекурсивно рассматривая левое и правое поддеревья (корнями которых также являются их элементы с максимальными приоритетами, и так далее), приходим к выводу, что положение каждого элемента дерева задано однозначно, зависит от пары (ключ — приоритет) и не зависит от порядка добавления элементов в дерево.

• Примеры декартовых деревьев
• Treap example 1.jpg
• Treap example 2.jpg

Можно показать, что доля двоичных деревьев поиска из N элементов, высота которых не превышает ⌈4log₂N⌉, стремится к 100%. Этот факт позволяет применить идею рандомизированного алгоритма: если приоритеты узлов назначаются при добавлении случайным образом, то вероятность того, что получившееся дерево будет иметь высоту, превышающую ⌈4log₂N⌉, становится пренебрежимо малой. Таким образом, дерево поиска со случайными приоритетами, элементы которого формируют пирамиду по приоритетам, позволяет выполнять основные операции со сложностью 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)

Файл:Treap merge.jpg

Объединение дерамид

Пусть даны две дерамиды 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)

Файл:Treap split.jpg

Разрезание дерамиды

Пусть дана дерамида 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 &lt= 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 пуста.