红黑树 (Red-Black Tree)

红黑树（Red-Black Tree, RBT）是一种自平衡二叉搜索树，广泛应用于操作系统内核调度（如 Linux CFS 调度器）以及主流编程语言的底层容器（如 C++ 的 std::set 与 std::map）。

---

红黑树的五大核心性质

1. 节点颜色：每个节点必须是黑色或红色。
2. 根节点特性：根节点必须是黑色。
3. 叶子节点特性：所有叶子节点（NIL 哨兵空节点）必须是黑色。
4. 红色约束：红色节点的子节点必须都是黑色（即不允许有两个连续的红色节点）。
5. 黑高一致：从任一节点到其所有后代叶节点的简单路径上，包含相同数量的黑色节点（称为黑高 \(\text{bh}\)）。

树高推论：由性质 4 与 5 可证明，一棵包含 \(n\) 个内部节点的红黑树，其高度至多为 \(2 \log_2(n + 1)\)。因此所有动态查找、插入和删除的最坏时间复杂度均为严格 \(\mathcal{O}(\log n)\)。

---

竞赛利器：GCC 内置红黑树 (__gnu_pbds::tree)

在算法竞赛中，手写标准红黑树的旋转与双黑修复代码通常长达 150~200 行，极易在比赛高压下写出 bug。C++ GCC 提供了标准库扩展 PBDS（Policy-Based Data Structures），其底层正是高度优化的红黑树（rb_tree_tag），且额外提供了手写平衡树才有的查询排名与第 \(k\) 小功能。

#include <iostream>
// 引入 PBDS 头文件
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

// 定义支持查询名次与第 k 小的红黑树
// tree<Key, Mapped, Cmp, Tag, Node_Update>
template <typename T>
using ordered_set = tree<
    T,
    null_type,
    std::less<T>,
    rb_tree_tag,
    tree_order_statistics_node_update
>;

int main() {
    ordered_set<int> rbt;

    // 1. 插入与删除 O(log n)
    rbt.insert(10);
    rbt.insert(20);
    rbt.insert(5);
    rbt.erase(20);

    // 2. order_of_key(x): 返回严格小于 x 的元素个数 (即 0-indexed 名次)
    // 相当于平衡树中的 rank(x) - 1
    int rank = rbt.order_of_key(10); // 返回 1 (因为只有 5 比 10 小)

    // 3. find_by_order(k): 返回排名第 k 小元素的迭代器 (0 <= k < size)
    // 相当于平衡树中的 kth(k + 1)
    auto it = rbt.find_by_order(0);  // 返回指向 5 的迭代器
    if (it != rbt.end()) {
        std::cout << "第 0 小元素: " << *it << "\n";
    }

    return 0;
}

---

优雅实现：左倾红黑树 (Left-Leaning Red-Black Tree)

由著名计算机科学家 Robert Sedgewick 提出，将红黑树与 2-3 树严格等价（红色边只允许作为左斜边）。通过以下三条极简规则维持平衡，彻底消除了传统红黑树复杂的分类讨论：

1. 若右孩子为红、左孩子为黑：左单旋；
2. 若左孩子为红、且左孩子的左孩子也为红：右单旋；
3. 若左右孩子皆为红：颜色翻转 (Color Flip)。

template <typename T>
struct LLRBTree {
    static constexpr bool RED = true;
    static constexpr bool BLACK = false;

    struct Node {
        T val;
        bool color;
        int size;
        Node *left = nullptr;
        Node *right = nullptr;
        Node(T v, bool c) : val(v), color(c), size(1) {}
    };

    Node *root = nullptr;

    bool is_red(Node *u) const { return u ? u->color == RED : false; }
    int get_size(Node *u) const { return u ? u->size : 0; }

    void update(Node *u) {
        if (u) u->size = 1 + get_size(u->left) + get_size(u->right);
    }

    Node* rotate_left(Node *h) {
        Node *x = h->right;
        h->right = x->left;
        x->left = h;
        x->color = h->color;
        h->color = RED;
        update(h);
        update(x);
        return x;
    }

    Node* rotate_right(Node *h) {
        Node *x = h->left;
        h->left = x->right;
        x->right = h;
        x->color = h->color;
        h->color = RED;
        update(h);
        update(x);
        return x;
    }

    void flip_colors(Node *h) {
        h->color = !h->color;
        if (h->left) h->left->color = !h->left->color;
        if (h->right) h->right->color = !h->right->color;
    }

    Node* insert(Node *h, T val) {
        if (!h) return new Node(val, RED);
        if (val < h->val) h->left = insert(h->left, val);
        else if (val > h->val) h->right = insert(h->right, val);

        // 核心三步自平衡修复
        if (is_red(h->right) && !is_red(h->left))      h = rotate_left(h);
        if (is_red(h->left) && is_red(h->left->left)) h = rotate_right(h);
        if (is_red(h->left) && is_red(h->right))       flip_colors(h);

        update(h);
        return h;
    }

    void insert(T val) {
        root = insert(root, val);
        root->color = BLACK;
    }
};