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

Редактирование данной статьи ещё не завершено.

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

Файл: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).

Файл:Treap trees height comparison.jpg

Декартово дерево на декартовой плоскости

Описанная структура данных называется декартовым деревом (дерамидой, англ. 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 <= 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(t); }

void dispose(TreapNode *n) { if (n == NULL) return; dispose(n->l); dispose(n->r); delete n; }