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

1️⃣ Как кратко ответить

Декартово дерево — это структура данных, которая объединяет свойства бинарного дерева поиска и кучи. В узлах дерева хранятся пары значений (ключ, приоритет), где ключи организованы как в бинарном дереве поиска, а приоритеты — как в куче. Это позволяет эффективно выполнять операции вставки, удаления и поиска.

2️⃣ Подробное объяснение темы

Декартово дерево, также известное как treap (от слов "tree" и "heap"), — это структура данных, которая сочетает в себе свойства бинарного дерева поиска и кучи. Это позволяет эффективно выполнять операции, такие как вставка, удаление и поиск, с логарифмической сложностью в среднем случае.

Основные свойства

1. Бинарное дерево поиска (BST): В каждом узле хранится ключ, и для любого узла все ключи в левом поддереве меньше ключа этого узла, а все ключи в правом поддереве больше.

2. Куча: В каждом узле также хранится приоритет, и приоритеты организованы так, что приоритет родительского узла всегда больше (или меньше, в зависимости от типа кучи) приоритетов его дочерних узлов.

Зачем это нужно

Декартово дерево полезно, когда требуется поддерживать динамическое множество данных с возможностью быстрого поиска, вставки и удаления. Оно объединяет преимущества бинарного дерева поиска и кучи, что делает его эффективным для задач, где важны обе эти структуры данных.

Как это работает

При вставке нового элемента в декартово дерево, элемент сначала добавляется как в бинарное дерево поиска по ключу. Затем, если приоритет нового элемента нарушает свойство кучи, выполняются вращения (повороты) для восстановления этого свойства.

Пример кода

#include <iostream>
#include <cstdlib>
#include <ctime>
​
// Структура для представления узла декартова дерева
struct Node {
    int key; // Ключ узла
    int priority; // Приоритет узла
    Node* left; // Левое поддерево
    Node* right; // Правое поддерево
​
    Node(int k) : key(k), priority(std::rand()), left(nullptr), right(nullptr) {}
};
​
// Функция для выполнения правого поворота
Node* rotateRight(Node* y) {
    Node* x = y->left;
    y->left = x->right;
    x->right = y;
    return x;
}
​
// Функция для выполнения левого поворота
Node* rotateLeft(Node* x) {
    Node* y = x->right;
    x->right = y->left;
    y->left = x;
    return y;
}
​
// Вставка нового узла в декартово дерево
Node* insert(Node* root, int key) {
    if (!root) {
        return new Node(key);
    }
​
    if (key < root->key) {
        root->left = insert(root->left, key);
​
        // Если приоритет левого дочернего узла больше, выполняем правый поворот
        if (root->left->priority > root->priority) {
            root = rotateRight(root);
        }
    } else {
        root->right = insert(root->right, key);
​
        // Если приоритет правого дочернего узла больше, выполняем левый поворот
        if (root->right->priority > root->priority) {
            root = rotateLeft(root);
        }
    }
    return root;
}
​
// Обход дерева в порядке возрастания ключей
void inorder(Node* root) {
    if (root) {
        inorder(root->left);
        std::cout << "Key: " << root->key << ", Priority: " << root->priority << std::endl;
        inorder(root->right);
    }
}
​
int main() {
    std::srand(std::time(0)); // Инициализация генератора случайных чисел
​
    Node* root = nullptr;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);
​
    inorder(root);
​
    return 0;
}

Пояснение к коду

• Node: Структура, представляющая узел дерева, содержащая ключ, приоритет и указатели на левое и правое поддеревья.
• rotateRight и rotateLeft: Функции для выполнения поворотов, которые восстанавливают свойство кучи.
• insert: Рекурсивная функция для вставки нового узла. Она сначала вставляет узел как в бинарное дерево поиска, а затем выполняет повороты, если это необходимо для поддержания свойства кучи.
• inorder: Функция для обхода дерева в порядке возрастания ключей, что демонстрирует структуру дерева.

Декартово дерево — это мощный инструмент для управления динамическими множествами данных, который сочетает в себе преимущества двух фундаментальных структур данных.