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

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

Декартово дерево (Cartesian tree, англ. Treap) — это рандомизированная структура данных, которая одновременно является бинарным деревом поиска (BST) по одному параметру и бинарной кучей (heap) по другому. Это гибрид, объединяющий преимущества обоих.

Определение

Декартово дерево содержит элементы (x, y), где:

• x — ключ для упорядочения (как в BST)
• y — приоритет (как в heap), обычно случайный

Проприетарства:

1. BST свойство по x: левое поддерево < родитель < правое поддерево
2. Heap свойство по y: приоритет родителя >= приоритеты детей (max-heap)

Пример структуры

Дерево с элементами [(5,10), (3,20), (7,15), (1,8), (4,12)]:

        (3,20)           -- Корень имеет максимальный приоритет (20)
        /      \
      (1,8)    (5,10)    -- BST: 1 < 3 < 5
        \      /  \
       (4,12) (4,12) (7,15)
       
Проверка:
- BST: 1 < 3 < 5, и 4 < 5 < 7 ✓
- Heap: 20 > 8, 20 > 10, 10 > 12, 10 > 15 ✓

Реализация на C++

#include <random>
#include <iostream>
using namespace std;

struct Node {
    int key, priority;
    Node *left, *right;
    
    Node(int k, int p) 
        : key(k), priority(p), left(nullptr), right(nullptr) {}
};

class Treap {
private:
    Node* root;
    mt19937 rng{random_device{}()};
    uniform_int_distribution<> dis{1, INT_MAX};
    
    // Правый поворот
    Node* rotateRight(Node* x) {
        Node* y = x->left;
        x->left = y->right;
        y->right = x;
        return y;
    }
    
    // Левый поворот
    Node* rotateLeft(Node* x) {
        Node* y = x->right;
        x->right = y->left;
        y->left = x;
        return y;
    }
    
    Node* insert(Node* node, int key) {
        if (node == nullptr) {
            return new Node(key, dis(rng));
        }
        
        if (key < node->key) {
            node->left = insert(node->left, key);
            // Если нарушено heap свойство, повернуть
            if (node->left->priority > node->priority) {
                node = rotateRight(node);
            }
        } else if (key > node->key) {
            node->right = insert(node->right, key);
            // Если нарушено heap свойство, повернуть
            if (node->right->priority > node->priority) {
                node = rotateLeft(node);
            }
        }
        
        return node;
    }
    
    Node* erase(Node* node, int key) {
        if (node == nullptr) return nullptr;
        
        if (key < node->key) {
            node->left = erase(node->left, key);
        } else if (key > node->key) {
            node->right = erase(node->right, key);
        } else {
            // Нашли узел для удаления
            // Двигаем узел вниз через повороты
            if (node->left == nullptr) {
                Node* temp = node->right;
                delete node;
                return temp;
            } else if (node->right == nullptr) {
                Node* temp = node->left;
                delete node;
                return temp;
            } else {
                // Если есть оба ребёнка, повернуть более приоритетное вверх
                if (node->left->priority > node->right->priority) {
                    node = rotateRight(node);
                    node->right = erase(node->right, key);
                } else {
                    node = rotateLeft(node);
                    node->left = erase(node->left, key);
                }
            }
        }
        
        return node;
    }
    
    bool search(Node* node, int key) {
        if (node == nullptr) return false;
        if (key == node->key) return true;
        if (key < node->key) return search(node->left, key);
        return search(node->right, key);
    }

public:
    Treap() : root(nullptr) {}
    
    void insert(int key) {
        root = insert(root, key);
    }
    
    void erase(int key) {
        root = erase(root, key);
    }
    
    bool search(int key) {
        return search(root, key);
    }
};

Временная сложность

Рандомизация гарантирует, что в среднем дерево сбалансировано, что избегает худших случаев обычных BST.

Практические применения

1. Встроенная сортировка

vector<int> treapSort(vector<int>& arr) {
    Treap treap;
    for (int x : arr) {
        treap.insert(x);
    }
    // Обход in-order даст отсортированный массив
    vector<int> result;
    // inorderTraversal(root, result);
    return result;
}

2. Поиск k-го наименьшего элемента

int findKth(Node* root, int k) {
    // Добавить размер поддерева в каждый узел
    // Использовать для быстрого поиска
    int leftSize = getSize(root->left);
    if (k <= leftSize) {
        return findKth(root->left, k);
    } else if (k == leftSize + 1) {
        return root->key;
    } else {
        return findKth(root->right, k - leftSize - 1);
    }
}

3. Балансирование при вставке

// Вставка случайного элемента всегда берёт логарифмическое время
// благодаря случайным приоритетам
for (int i = 0; i < n; i++) {
    treap.insert(randomElement());
    // O(log i) амортизированно
}

Сравнение с другими структурами

Преимущества

1. Простота реализации: Чем Random приоритеты, простая логика
2. Хорошая на практике: Часто работает быстрее AVL и RB деревьев
3. Вероятностная гарантия: Рандомизация гарантирует баланс
4. Гибкость: Легко модифицировать для различных задач

Недостатки

1. Недетерминированность: Производительность может варьироваться
2. Требует random: Нужен хороший генератор случайных чисел
3. Не гарантирует худший случай: Теоретически O(n) в худшем случае

Пример использования

int main() {
    Treap treap;
    
    // Вставка
    treap.insert(5);
    treap.insert(3);
    treap.insert(7);
    treap.insert(1);
    treap.insert(9);
    
    // Поиск
    cout << treap.search(5) << endl;  // 1 (true)
    cout << treap.search(4) << endl;  // 0 (false)
    
    // Удаление
    treap.erase(5);
    cout << treap.search(5) << endl;  // 0 (false)
    
    return 0;
}

Вывод

Декартово дерево (Treap) — это элегантная структура данных, которая демонстрирует мощь рандомизации в алгоритмах. Для backend-разработчиков это полезно для реализации высокопроизводительных систем хранения данных, где требуется амортизированная логарифмическая сложность операций без сложности явной балансировки.