【DSA】Red-Black Tree

红黑树是一种自平衡二叉查找树，通过颜色约束和旋转操作保证动态操作的高效性，在插入、删除等操作后仍能维持近似平衡，确保最坏情况下的时间复杂度为 O(\log n)。以下从核心性质、操作原理、应用场景等维度系统解析：

🔴 ⚫ 核心性质与平衡原理

红黑树必须满足5条性质：

节点颜色：每个节点非红即黑。
根节点黑色：根节点必须是黑色。
叶子节点黑色：所有叶子节点（NIL哨兵节点）均为黑色1,3。
红色节点限制：红色节点的子节点必须是黑色（不存在连续红色节点）。
黑高一致：从任意节点到其后代叶子节点的路径包含相同数量的黑色节点（称为黑高，Black Height）1,6。

💡 平衡性保障：
性质4和5确保最长路径长度不超过最短路径的2倍（最长路径黑红相间，最短路径全黑）3。
含 n 个节点的红黑树高度满足 h \leq 2\log_2(n+1)，避免退化为链表1,6。

🔄 核心操作：旋转与修复

⚙️ 旋转操作（调整结构）

左旋：以节点 x 为支点，将其右子节点 y 提升为父节点，x 成为 y 的左子树，并调整子树关系。
右旋：以节点 y 为支点，将其左子节点 x 提升为父节点，y 成为 x 的右子树1,6。作用：调整拓扑结构，不破坏二叉搜索树性质。

➕ 插入操作（默认染红）

插入新节点时初始设为红色（避免破坏黑高），再根据父节点颜色修复：

Case 1：父节点为黑 → 直接插入。
Case 2：父节点和叔节点均为红 → 将父、叔染黑，祖父染红，递归修复祖父节点。
Case 3：父节点红、叔节点黑 → 通过旋转调整：
- LL/RR型：父节点与祖父节点互换颜色，右旋/左旋祖父。
- LR/RL型：先旋转父节点转换为LL/RR型，再按上一步处理1,5。 插入修复策略总结：
  父节点 叔节点 操作
  黑 - 直接插入
  红红父、叔染黑，祖父染红，递归修复祖父
  红黑旋转祖父节点并交换颜色（具体见Case 3）

父节点	叔节点	操作
黑	-	直接插入
红	红	父、叔染黑，祖父染红，递归修复祖父
红	黑	旋转祖父节点并交换颜色（具体见Case 3）

✖️ 删除操作（双黑修复）

删除黑色节点可能破坏黑高，需引入双黑节点（逻辑标记，代表需补足一个黑色）：

Case 1：被删节点为红 → 直接删除。
Case 2：被删节点为黑，子节点为红 → 用子节点替代并染黑。

Case 3：被删节点为黑，子节点为黑 → 删除后子节点标记为双黑，分情况修复：

兄弟节点红：旋转父节点，转换为兄弟节点黑的情况。

兄弟节点黑：根据兄弟子节点的颜色进行旋转和重染色3,6。 双黑修复策略总结：

兄弟节点颜色	兄弟子节点颜色	操作
红	任意	旋转父节点，转换为兄弟黑
黑	远侄节点红	旋转父节点，交换父与兄弟颜色，远侄染黑
黑	远侄黑、近侄红	旋转兄弟节点，交换兄弟与近侄颜色，转换为上一种情况
黑	兄弟子节点全黑	兄弟染红，父节点标记为双黑（若父原为红则染黑；若黑则递归修复父节点）

⚖️ 红黑树 vs. AVL树

特性	红黑树	AVL树
平衡标准	黑高一致（非严格平衡）	左右子树高度差 ≤ 1
插入/删除	旋转次数少，效率高	频繁旋转，效率较低
查找效率	略低于AVL（树高更高）	更高（树高更小）
适用场景	频繁增删的动态数据集	查询为主的数据集

💡 工程选择：Java的TreeMap、Linux内核调度器、数据库索引（如MongoDB）均采用红黑树，因其在动态操作中综合性能更优1,4。

🛠️ 应用场景与工程实践

数据库索引：MongoDB使用红黑树实现范围查询，兼顾插入与查询效率1。
语言标准库：
- Java的TreeMap、TreeSet基于红黑树，保证有序性操作高效4。
- C++ STL的map、set同样采用红黑树实现6。
操作系统内核：Linux内核用红黑树管理进程调度队列和内存区域1。
文件系统：如Ext3文件系统使用红黑树跟踪目录项，加速文件查找6。

💻 代码实现关键（C++示例）

enum Color { RED, BLACK };

template<typename T>
struct RBTreeNode {
    T key;
    Color color;
    RBTreeNode* left;
    RBTreeNode* right;
    RBTreeNode* parent;
    RBTreeNode(T k) : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

template<typename T>
class RBTree {
public:
    RBTree() : root(nullptr) {}
    
    void Insert(T key) {
        RBTreeNode<T>* node = new RBTreeNode<T>(key);
        // 1. 二叉查找树插入
        RBTreeNode<T>* parent = nullptr;
        RBTreeNode<T>* current = root;
        while (current) {
            parent = current;
            if (key < current->key) current = current->left;
            else current = current->right;
        }
        node->parent = parent;
        if (!parent) root = node;
        else if (key < parent->key) parent->left = node;
        else parent->right = node;
        
        // 2. 修复红黑树性质
        InsertFixup(node);
    }

private:
    void InsertFixup(RBTreeNode<T>* node) {
        while (node->parent && node->parent->color == RED) {
            if (node->parent == node->parent->parent->left) {
                RBTreeNode<T>* uncle = node->parent->parent->right;
                if (uncle && uncle->color == RED) { // Case 2: 叔节点红
                    node->parent->color = BLACK;
                    uncle->color = BLACK;
                    node->parent->parent->color = RED;
                    node = node->parent->parent;
                } else { // Case 3: 叔节点黑
                    if (node == node->parent->right) {
                        node = node->parent;
                        LeftRotate(node);
                    }
                    node->parent->color = BLACK;
                    node->parent->parent->color = RED;
                    RightRotate(node->parent->parent);
                }
            } else { // 对称处理
                // ...
            }
        }
        root->color = BLACK; // 根节点始终为黑
    }

    void LeftRotate(RBTreeNode<T>* x) {
        RBTreeNode<T>* y = x->right;
        x->right = y->left;
        if (y->left) y->left->parent = x;
        y->parent = x->parent;
        if (!x->parent) root = y;
        else if (x == x->parent->left) x->parent->left = y;
        else x->parent->right = y;
        y->left = x;
        x->parent = y;
    }

    RBTreeNode<T>* root;
};

💎 总结

红黑树通过颜色约束与旋转策略在动态操作中维持近似平衡，其设计权衡了严格平衡（AVL树）与操作效率，成为工程实践中高频增删场景的首选结构。核心在于：

插入修复：通过递归染色和旋转消除连续红节点；
删除修复：双黑节点标记与兄弟节点协同调整黑高；
性能优势：牺牲部分查找效率换取更高的插入/删除吞吐量1,6。深入理解红黑树，可掌握数据结构的动态平衡本质，并为数据库、操作系统等底层系统开发奠定基础。