数据结构：红黑树（Red-Black Tree）

从AVL树的“烦恼”说起

如何用“颜色”来定义“大致平衡”？—— 红黑树的五个规则

五个规则如何保证“大致平衡”？

用 C/C++ 代码定义红黑树的结构

定义颜色和节点结构

定义树的结构和哨兵节点

从AVL树的“烦恼”说起

我们从已经了解的 AVL 树出发。AVL 树的出发点是什么？

是为了解决二叉搜索树（Binary Search Tree, BST）在最坏情况下退化成链表的问题。它的核心思想是：强制平衡。它有一个非常严格的规定：“任意节点左右子树的高度差 ≤ 1”。

这个规定很有效，保证了树的高度始终在 O(logN) 级别，因此查找效率非常高。但它的“烦恼”也来源于此：

📌 为了维持这个严格的平衡，AVL 树的插入和删除操作可能会导致频繁的旋转 (Rotation)。有时候，仅仅插入一个节点，就可能需要从插入点一直回溯到根节点，进行多次旋转。旋转操作本身是有开销的。

既然“绝对平衡”的维护成本有点高，我们能不能稍微“放松”一点要求？我们不追求“完美身高”，只追求“身材匀称”，只要最长路径和最短路径的长度别差得太离谱，那它的查找效率不也能保证在 O(logN) 吗？❓❓❓

这个“放松要求，换取插入/删除时更少操作”的想法，就是红黑树诞生的根本动机。

第一性原理推导:

目标: 保持树的查找效率，即树的高度维持在 O(logN)。
现有方案: AVL 树通过严格限制左右子树高度差来实现。
痛点: 维护严格平衡的成本（旋转次数）较高。
新思路: 寻找一种弱一点的平衡标准。这个标准必须足够强，以保证树高为 O(logN)；又必须足够弱，以减少插入/删除时维护平衡的代价。

红黑树就是这个新思路的杰出实现。它放弃了用“高度”这个属性来做限制，而是引入了一个全新的、更巧妙的属性：颜色 (Color)。

如何用“颜色”来定义“大致平衡”？—— 红黑树的五个规则

好，我们现在给每个节点增加一个属性：color，它可以是红色 (RED)或黑色 (BLACK)。通过一些“颜色规则 (Coloring Rules)”来限制树的形态，保证从根到任意叶子的路径长度不会差太多。

1. 二叉搜索树的复杂度依赖高度

查找（Search）复杂度 = O(h)，其中 h 是树高。
如果 h 太大（比如退化成链表），复杂度退化为 O(N)。
所以我们必须保证 h = O(log N)。

2. 最短路径长度与节点数的关系

在一棵二叉树里，最短路径长度（记为 h_min）指从根到某个叶子所经过的边数。
如果所有路径至少有 h_min 个节点（或边），那么这棵树至少包含：2^(h_min) - 1 个节点（这是满二叉树的下界）。
因此：N ≥ 2^(h_min) - 1 ⇒ h_min ≤ log2(N+1)

3. 如果最长路径 ≤ 2 × 最短路径

设：

h_min = 最短路径高度
h_max = 最长路径高度 = 树的高度

如果能保证：h_max ≤ 2 * h_min

那么结合上面的不等式：h_min ≤ log2(N+1) ⇒ h_max ≤ 2 * log2(N+1)

于是我们得到了：h_max = O(log N)

我们的最终目标是证明：

一棵红黑树从根到最远叶子节点的路径长度，不会超过到最近叶子节点路径长度的两倍。

如果能证明这一点，就说明树的高度依然是 O(logN)，我们的目标就达成了。

我们来一步步推导出这些规则：

1️⃣：每个节点要么是红色，要么是黑色。

这是最基本定义，就像说“游戏里的棋子要么是黑的，要么是白的”。没有它，后续规则无从谈起。

2️⃣：根节点是黑色。

这条规则不是强制性的，但它能简化很多问题。可以把它看作一个“基准”或“锚点”。

如果根节点是红色，它可能会违反其他规则（比如后面会提到的“红色节点的子节点不能是红色”），所以干脆定为黑色，让处理更统一。

3️⃣：所有叶子节点都是黑色。

这里的“叶子节点”比较特殊，它不是指最后一个有数据的节点，而是指其下方的 NULL 指针。

在红黑树的实现中，我们通常会用一个统一的、黑色的哨兵节点 (Sentinel Node) 来代表所有的 NULL。

这样做的好处是，处理边界情况（比如一个节点只有一个子节点）时，我们不需要写大量的 if (node->left != NULL) 判断，因为它的 left 和 right 总是指向一个有效的（哨兵）节点。这纯粹是为了简化代码实现。

至此，我们有了基本的颜色框架。但这些还不足以保证平衡。现在，我们需要引入真正限制树“形状”的规则。

4️⃣：红色节点的子节点必须是黑色的。 (也就是说，不能有两个连续的红色节点)

这是实现“放松平衡”的核心规则之一。如果允许红色节点串在一起（红->红->红...），那这条路径就会被无限制地拉长，树就会失衡。

这条规则强制打断了“红色路径”，确保了从根到叶子的路径上，红色节点不会连续出现。

5️⃣：从任一节点到其每个叶子（NIL 哨兵节点）的所有路径，都包含相同数目的黑色节点。

这是另一条核心规则，也是最难理解但最关键的一条。它定义了一个叫做“黑高 (Black-Height)”的概念。

这条规则强制要求，无论你从一个节点 x 出发，走左边还是走右边，到达终点（叶子）时，路上经过的黑色节点数量必须完全一样。这就像给树建立了一个“黑色的骨架”，这个骨架是完美平衡的。红色节点则可以看作是“填充”在这个黑色骨架之间的节点。

五个规则如何保证“大致平衡”？

现在我们来验证一下，这五条规则是否达成了我们的最终目标：最长路径 <= 2 * 最短路径。

📍最短路径:

考虑从根节点到一个叶子节点的最短路径。这条路径上会包含最少的节点。要让节点数最少，我们就应该尽量少放红色节点。

根据规则4，红色节点不能连续，所以最短的路径就是一条纯黑色的路径。这条路径的长度就是这棵树的黑高 (Black-Height)，我们记为 bh。

📌最长路径:

要让路径最长，我们就应该塞进尽可能多的红色节点。根据规则4，每两个黑色节点之间最多只能插入一个红色节点（黑 -> 红 -> 黑 -> 红 ...）。

由于规则5保证了任何路径上的黑色节点数量都是 bh，那么在最长路径上，我们最多也就能塞进 bh 个红色节点。

所以：

最短路径长度 = bh (全是黑色节点)
最长路径长度 <= bh (黑色节点) + bh (红色节点) = 2 * bh

结论：最长路径长度 <= 2 * 最短路径长度。

这个结论证明了红黑树的高度始终保持在 O(logN) 级别。我们成功地用五条看似无关的颜色规则，间接实现了树的平衡，而且这个平衡比 AVL 树更“宽松”。这种宽松，将为我们后续的插入和删除操作带来更低的维护成本。

用 C/C++ 代码定义红黑树的结构

好了，理论推导结束。我们现在开始写代码，一步步定义出红黑树的节点和树的结构。

定义颜色和节点结构

首先，我们需要一个 enum 来表示颜色。然后定义节点结构 RBTNode。

除了BST原有的 key、left、right 指针，我们还需要 color 属性和一个指向父节点 (parent) 的指针。父节点指针在后续的旋转和调整中非常有用，可以避免复杂的递归或栈来寻找父节点。

// 使用 C 风格的代码，不涉及高级语法和STL#include <stdio.h>// 专有名称: 颜色 (Color)
typedef enum {RED,    // 红色BLACK   // 黑色
} Color;// 专有名称: 红黑树节点 (Red-Black Tree Node)
typedef struct RBTNode {int key;              // 键值Color color;          // 颜色struct RBTNode *left;   // 左子节点指针struct RBTNode *right;  // 右子节点指针struct RBTNode *parent; // 父节点指针
} RBTNode;

这段代码非常基础，就是定义了我们讨论中需要的所有元素：键值、颜色、以及三个方向的指针

定义树的结构和哨兵节点

根据规则3，我们需要一个黑色的哨兵节点来代表所有的 NULL 叶子。我们可以定义一个全局的哨兵节点 NIL。树本身可以用一个指向根节点的指针来表示。

// 接着上面的代码// 哨兵节点 (Sentinel Node)，代表所有的NULL叶子
RBTNode* NIL;// 红黑树结构，本质上是一个指向根节点的指针
typedef struct RedBlackTree {RBTNode* root;
} RedBlackTree;// 初始化函数，用于创建NIL节点
void initializeNIL() {NIL = new RBTNode; // 在C++中用new，在C中用mallocNIL->color = BLACK;NIL->key = 0; // key值无所谓NIL->left = NULL;NIL->right = NULL;NIL->parent = NULL;
}

为什么需要 NIL 哨兵节点？

想象一下，如果没有 NIL，当你想访问 node->left->color 时，你必须先检查 node->left是不是 NULL。而有了 NIL，任何一个节点的 left 和 right 指针，要么指向一个有效的数据节点，要么指向 NIL。

因为 NIL 是一个有确定颜色（黑色）的真实节点，所以你可以安全地访问 node->left->color，这会让代码变得非常整洁。

一个新创建的树，其根节点应该指向 NIL。

// 创建一棵空树
RedBlackTree* createRedBlackTree() {RedBlackTree* tree = new RedBlackTree; // C: mallocif (NIL == NULL) {initializeNIL(); // 确保NIL只被初始化一次}tree->root = NIL; // 空树的根指向NILreturn tree;
}

到目前为止，我们已经成功地：