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

Ниже представлена реализация и примеры работы обычного декартова дерева с функциями insert, erase, build.

Изучение данной структуры является промежуточным шагом в изучении более мощной её вариации - декартова дерева по неявному ключу.

Структура Node

Структура, из экземпляров которой и будет состоять дерево. Здесь и далее key будет означать ключ, priority - приоритет, l - указатель на левого потомка вершины, r - указатель на правого потомка вершины.

struct Node {
    int key, priority;
    Node *l, *r;
    Node(int x, int y): key(x), priority(y), l(0), r(0) {}
};
typedef Node* pNode;

Функции merge и split

Почти все функции декартова дерева выражаются через две основные: split и merge, поэтому сначала дадим их реализацию.

split

Функция split принимает указатель на вершину t и ключ x, возвращает вершины l и r - указатели на корни левого и правого деревьев после разделения.

void split(pNode t, int x, pNode &l, pNode &r) {
    if (!t) { 
        l = 0;
        r = 0;
    } else if (t->key > x) {
        split(t->l, x, l, t->l); 
        r = t;
    } else {
        split(t->r, x, t->r, r); 
        l = t;
    }
}

merge

Функция merge принимает указатели на корни двух поддеревьев l и r, и возвращает указатель на новый корень r. Важно, чтобы ключи в левом поддереве были строго меньше ключей в правом поддереве.

void merge(pNode &t, pNode l, pNode r) {
    if (!l) { 
        t = r;
    } else if (!r) { 
        t = l;
    } else if (l->priority < r->priority) {
        merge(l->r, l->r, r); 
        t = l;
    } else {
        merge(r->l, l, r->l); 
        t = r;
    }
}

Добавление и удаление

add

Чтобы вставить вершину a с ключом a->key и приоритетом a->priority спустимся по дереву до первого элемента t, у которого приоритет окажется больше a->priority, новая вершина будет стоять на месте этой вершины t. Произведём split от этой вершины и ключа a->key, полученные поддеревья l и r станут соответственно левым и правым поддеревом новой вершины.

void add(pNode &t, pNode a) {
    if (!t) {
        t = a;
    } else if (a->priority < t->priority) {
        split(t, a->key, a->l, a->r); 
        t = a;
    } else {
        if (t->key < a->key) {
            add(t->r, a);
        } else { 
            add(t->l, a);
        }
    }
}

remove

Чтобы удалить вершину с ключом key также рекурсивно спустимся до вершины t с соответствующим ключом, затем выполним merge для её левого и правого поддерева. После merge не забудем удалить вершину.

void remove(pNode t, int key) {
    if (!t) {
        return;
    }
    if (t->key == key) {
        pNode tmp = t;
        merge(t, t->l, t->r);
        delete tmp;
    } else {
        if (t->key < key) {
            eraser(t->r, key);
        } else {
            eraser(t->l, key);
        }
    }
} 

Построение дерева

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

Линейное построение

Линейное построение стоит применять в том случае, если вы не можете контролировать приоритеты и возможно вырождение дерева в цепочку. Стоит также заметить, что линейное построение, приведённое ниже, работает только с данными, отсортированными по ключам.

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

pNode build(vector<pair<int, int>> &v) {
    stack<pNode> st;
    int x, y;
    x = v.begin()->first;
    x = v.begin()->second;
    st.emplace(new Node(x, y));
    for (int i = 1; i < v.size(); ++i) {
        x = v[i].first;
        y = v[i].second;
        pNode t = new Node(x, y);
        pNode next = 0;
        while (st.size() && st.top()->priority > y) {
            next = st.top();
            st.pop();
        }
        if (st.size()) {
            st.top()->r = t;
        }
        t->l = next;
        st.emplace(t);
    }
    while (st.size() > 1) {
        st.pop();
    }
    return st.top();
}

Легко заметить, что каждая вершина ровно однажды попадает в стек и ровно однажды оттуда выталкивается, следовательно сложность алгоритма линейно зависит от количества вершин.

Выбор приоритета

Выше было замечено, что в худшем случае декартово дерево может вырождаться в цепочку. Этого можно избегать, если у нас есть возможность самостоятельно выбирать приоритеты. Если приоритеты являются случайными величинами с равномерным распределением, то можно показать, что средняя глубина вершины будет порядка логарифма от количества вершин [1].

Хороший рандом в C++

Как было показано в [2], встроенный rand() может подвести в самый неожиданный момент. Вместо него можно использовать следующие варианты:

int r = (rand() << 16) + rand();

или

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int r = rnd();

Задачи

Вставка и удаление

• Задача №2782. Следующий
• Задача №756. Минимум на отрезке

Линейное построеине

• Задача №2781. Декартово дерево

Дальнейшее чтение

1. Викиконспекты - Декартово дерево
2. Codeforces - Don’t use rand(): a guide to random number generators in C++