Декартово дерево по неявному ключу

treap_implicit.cpp

#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;


// Узел декартового дерева по неявному ключу. Главное отличие - мы больше не храним
// ключ в явном виде, вместо этого мы просто храним размер поддерева с корнем
// в данном узле. Доступ к элементам дерева будет осуществляться по вычисляемому
// "номеру" вершины, равному её порядковому номеру при прямом (Л-К-П) обходе.
struct Node {
    int y;   // Как и прежде, "приоритет" вершины
    int sz;  // Хранимый размер поддерева

    int val; // Хранимое значение в узле.

    Node *l, *r; // Указатели на левого и правого ребёнка
};

// Создание нового узла. Здесь мы должны инициализировать все поля узла, и при этом
// мы вполне вольны разместить вершину там, где хотим. Для простоты пользуемся системным
// выделителем памяти, однако одна из возможных оптимизаций - предвыделение всех необходимых
// ресурсов и написание собственного (более простого/быстрого) выделителя.
Node *new_node(int val)
{
    Node *result = new Node;
    result->y = rand();
    result->sz = 1;     // По сути, новый узел задаёт нам декартово дерево из одного узла,
                        // и размер такого дерева будет равен 1.
    result->val = val;
    result->l = result->r = nullptr; // Не забываем указать, что у нового узла нет потомков
    return result;
}

// Получение размера поддерева. Функция гарантирует, что её выполнение не приведёт к ошибке
// даже при передаче ей пустого дерева.
int get_sz(Node *t)
{
    if (t == nullptr) { return 0; } // Полагаем размер пустого дерева равным нулю.
    return t->sz; // Считаем, что размер поддерева поддерживается корректно
}

// Пересчёт размера поддерева. Эту операцию надо выполнять каждый раз, когда с деревом происходят
// какие-либо изменения (то есть в любом split и merge) для поддержания корректности работы операций
// над деревом.
// Данная функция предполагает, что размеры потомков также являются корректными. Это обеспечивается
// в операциях split и merge за счёт их рекуррентной природы (размеры будут пересчитываться от листьев
// к корням после любого изменения)
void upd_sz(Node *t)
{
    if (t == nullptr) { return; }
    t->sz = 1 + get_sz(t->l) + get_sz(t->r);
}

// Код операции слияния (merge) остаётся ровно таким же, как и для декартового дерева по явному ключу:
// для неё важен только порядок вершины (y), мы же должны гарантировать соотношение значений ключей в
// левом и правом поддеревьях, но, поскольку у нас явного ключа нет, у нас "автомагически" получится
// верное дерево
Node *merge(Node* t1, Node *t2)
{
    if (t1 == nullptr) { return t2; }
    if (t2 == nullptr) { return t1; }
    if (t1->y > t2->y)
    {
        t1->r = merge(t1->r, t2);
        upd_sz(t1);
        return t1;
    }
    else
    {
        t2->l = merge(t1, t2->l);
        upd_sz(t2);
        return t2;
    }
}

// Разбиение дерева на два поддерева - одно с вершинами с порядковыми номерами [0..x), другое - [x..t->sz)
// Здесь придётся делать небольшие изменения: например, поскольку ключа уже нет, надо уметь его вычислить, зная
// размеры каждого поддерева.
void split(Node *t, int x, Node *&t1, Node *&t2)
{
    if (t == nullptr)
    {
        t1 = t2 = nullptr;
        return;
    }
    // Заметим, что порядковый номер текущей вершины в прямом обходе равен размеру её левого поддерева.
    // (Действительно, ведь в прямом обходе мы должны сначала пройти всех левых детей, прежде чем вернёмся
    // к корню). Следовательно, если размер текущего левого поддерева меньше, чем индекс разбиения, то
    // оно целиком отправится в первое дерево, а разбивать нам надо будет правое поддерево.
    if (get_sz(t->l) < x)
    {
        // Корень и всё левое поддерево должны отправиться в первое дерево-результат, а правое поддерево надо
        // продолжить разбивать. Вот только индекс разбиения будет уже другим: корень и левое поддерево содержат
        // get_sz(t->l) + 1 узел, и именно настолько надо уменьшить наш индекс разбиения.
        split(t->r, x - get_sz(t->l) - 1, t->r, t2);
        t1 = t;
    }
    else
    {
        // Текущая вершина находится правее индекса разбиения, следовательно, она должна отправиться во
        // второе дерево. При этом индекс разбиения трогать не нужно.
        split(t->l, x, t1, t->l);
        t2 = t;
    }
    upd_sz(t);
}

// Добавление и удаление элементов из дерева - такие же последовательности split/merge, как и в декартовом дереве
// с той лишь разницей, что теперь мы можем указывать, например, позицию, куда надо добавить новый элемент
Node *add(Node *t, int pos, int val)
{
    Node *t1, *t2;
    split(t, pos, t1, t2);
    Node* new_tree = new_node(val);
    return merge(merge(t1, new_tree), t2);
}

Node* remove(Node *t, int pos)
{
    Node *t1, *t2, *t3, *t4;
    split(t, pos, t1, t2);
    split(t2, pos + 1, t3, t4);
    t = merge(t1, t4);
    delete t3;
    return t;
}

// Создание дерева из массива - просто слияние текущего дерева с новыми деревьями, образованными из
// элементов заданного массива. Для простоты упаковываем исходный массив в вектор.
Node *from_vector(const vector<int>& v)
{
    Node *result = nullptr;
    for (int i = 0; i < v.size(); ++i)
    {
        result = merge(result, new_node(v[i]));
    }
    return result;
}

// Получение k-го элемента, по сути, аналогично получению k-й порядковой статистике в
// декартовом дереве по явному ключу
int get_value(Node *t, int pos)
{
    int my_idx = get_sz(t->l);
    if (pos < my_idx)
    {
        return get_value(t->l, pos);
    }
    else if (pos == my_idx)
    {
        return t->val;
    }
    else
    {
        return get_value(t->r, pos - my_idx - 1);
    }
}

// Перенести часть массива [l..r] в начало массива (как пример операции, производимой над "массивом", содержащимся в
// декартовом дереве)
Node *to_front(Node *t, int l, int r)
{
    Node *t1, *t2, *t3, *t4;
    // Дабы не думать над тем, как преобразовывать индексы при разделении,
    // сначала "отрежем" по правой границе, затем - по левой.
    split(t, r + 1, t1, t2);
    split(t1, l, t3, t4);
    // Теперь "вырезанная" часть находится в дереве t4, всё, что было левее - в t3,
    // что правее - в t2.
    return merge(merge(t4, t3), t2);
}

// Печать всего дерева. Просто обходим наше дерево как обычное бинарное дерево поиска,
// вместо того, чтобы каждый раз пользоваться get_value.
void print_tree(Node *t)
{
    if (t == nullptr) { return; }
    print_tree(t->l);
    cout << t->val << " ";
    print_tree(t->r);
}

int main()
{
    const int N = 15;
    vector<int> source_numbers;
    cout << "Generating random numbers..." << endl;
    for(int i = 0; i < N; ++i)
    {
        source_numbers.push_back(rand() % 100);
        cout << *source_numbers.rbegin() << " ";
    }
    cout << endl;
    Node *tree = from_vector(source_numbers);
    cout << "Numbers stored in the tree: " << endl;
    for(int i = 0; i < get_sz(tree); ++i)
    {
        cout << get_value(tree, i) << " ";
    }
    int l = 3, r = 8;
    cout << endl << "Bringing elements " << l << " thru " << r << " to front several times" << endl;
    const int times = 15;
    for(int i = 0; i < 15; ++i)
    {
        tree = to_front(tree, l, r);
        cout << "Iteration " << i + 1 << ", tree state: ";
        print_tree(tree);
        cout << endl;
    }
    cout << "Cleaning up..." << endl;
    while(get_sz(tree))
    {
        tree = remove(tree, 0);
    }
    return 0;
}

В 124 строчке кажется ошибка, там должно быть " split(t2, 1, t3, t4); ", а не pos+1, т.к. нужно удалить в t2 только первый элемент, именно он и равен pos.

В 124 строчке кажется ошибка, там должно быть " split(t2, 1, t3, t4); ", а не pos+1, т.к. нужно удалить в t2 только первый элемент, именно он и равен pos.

Похоже на то.

ТЫ МЕНЯ СПАС. Я У СЕБЯ ТАКОЙ БАГ ИСКАЛ часа 2
НАЧАЛ ГУГЛИТЬ И ТУТ ЭТО