一、为什么需要红黑树？
在编程中，我们经常需要一个动态维护有序数据的结构。比如：
std::map和std::set的底层实现- Linux内核的进程调度器
- 数据库的索引结构
如果使用普通的二叉搜索树（BST），极端情况下会退化成链表（如插入有序数据），导致查找效率从O(log n)降为O(n)。为了解决这个问题，红黑树（Red-Black Tree）应运而生。
二、红黑树的核心思想
红黑树是一种自平衡的二叉搜索树，它通过以下规则实现近似平衡：
红黑树的5大规则
- 每个节点非红即黑
- 根节点必须是黑色
- 红色节点的子节点必须是黑色（不能出现连续的红色）
- 从任意节点到其空子节点的路径上，黑色节点的数量必须相同
- 每个叶子节点（空节点）是黑色
为什么这些规则能保证效率？
- 最长路径 ≤ 2 × 最短路径
例如，如果最短路径有k个节点，最长路径最多有2k个节点。这确保了红黑树的高度始终在O(log n)范围内。
三、红黑树的插入操作详解
插入新节点时，红黑树需要通过变色 + 旋转维持平衡。以下是典型场景：
情况1：父节点是黑色
- 直接插入即可，无需调整。
情况2：父节点是红色
此时需要根据叔叔节点的颜色进行处理：
子情况1：叔叔是红色
- 操作：父节点、叔节点变黑，祖父节点变红，并继续向上处理。
祖父(黑) → 父(红) → 当前(红) 叔(红)子情况2：叔叔是黑色或不存在
需要通过旋转调整：
- LL型（当前节点在左子树的左子树）：右单旋 + 变色
- RR型（当前节点在右子树的右子树）：左单旋 + 变色
- LR型（当前节点在左子树的右子树）：左右双旋 + 变色
- RL型（当前节点在右子树的左子树）：右左双旋 + 变色
四、红黑树的代码实现
enum Color { RED, BLACK }; template <typename K, typename V> struct RBTreeNode { RBTreeNode* left; RBTreeNode* right; RBTreeNode* parent; std::pair<K, V> kv; Color color; RBTreeNode(const K& key, const V& value) : left(nullptr), right(nullptr), parent(nullptr), kv(key, value), color(RED) {} }; template <typename K, typename V> class RBTree { public: void insert(const K& key, const V& value) { // 二叉搜索树插入逻辑 // ... // 插入后调整平衡 fixInsert(newNode); } private: void fixInsert(RBTreeNode<K, V>* node) { while (node->parent && node->parent->color == RED) { // 处理四种情况 // ... } root->color = BLACK; } RBTreeNode<K, V>* root; };五、红黑树的应用场景
1.C++ STL容器
std::map和std::set默认使用红黑树实现（C++11）。- 插入/删除操作时间复杂度为
O(log n)。
2.Linux内核
- 完全公平调度器（CFS）使用红黑树管理进程队列。
- 快速找到下一个要运行的进程。
3.数据库索引
- MySQL 的 InnoDB 引擎使用 B+ 树（红黑树的扩展）作为索引结构。
