目录
Subcase 2.2: “三角”情况 (Triangle)
回顾与准备 —— 节点结构和旋转操作
在我们开始插入之前，必须先再次明确我们的“工具”。
数据结构：红黑树（Red-Black Tree）-CSDN博客
一个红黑树节点，首先是一个二叉搜索树 (Binary Search Tree, BST) 的节点。
我们需要存储数据，所以要有
int key。它是一个二叉树，所以需要指向左右子节点的指针
struct RBTNode *left和struct RBTNode *right。这是红黑树，我们需要用“颜色”这个属性来维持平衡，所以需要
Color color。在插入和删除后，我们常常需要从一个节点向上回溯到它的父节点、祖父节点等来进行调整（后面你会看到为什么）。如果没有一个直接的指针，我们就只能通过复杂的递归或者另外用一个栈来保存路径，这很低效。因此，为了方便调整，我们给节点增加一个
struct RBTNode *parent指针。
这就是我们上一部分定义的节点结构，每一样东西都有其存在的明确理由。
// 我们再次定义一遍，以保证讲解的完整性
// 专有名称: 颜色 (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;平衡的工具：旋转 (Rotation)
当树的结构变得不平衡时，我们需要一种方法来调整它，同时保持二叉搜索树的性质（即左子节点 < 父节点 < 右子节点）。这个调整的“手术刀”就是旋转。旋转分为左旋和右旋，它们是互为逆操作的。
左旋 (Left Rotation)：
假设我们有一个节点 x，它的右子节点是 y。对 x 进行左旋，意味着我们想让 y “上位”，成为 x 的父节点。
目标: 让
y成为新的根，x成为y的左孩子。约束: 必须维持BST性质。
y 的左子树（我们称之为 beta）怎么办？它原本在 x 和 y 之间。在旋转后，x 成了 y 的左孩子，那么 y 原来的左子树 beta 就没地方放了。
根据BST性质，beta 里的所有值都大于 x 且小于 y。因此，beta 最适合的位置就是成为 x 的新的右子树。
其他关系顺势调整：y 的父节点变成 x 原来的父节点，x 的父节点变成 y。
图解左旋 (对节点 x 左旋)：
parent parent
| |
x y
/ \ / \
a y ==> x c
/ \ / \
b c a ba,b,c代表子树 (alpha, beta, gamma)。x的右孩子指针从指向y变成指向b(y 的原左子树)。y的左孩子指针从指向b变成指向x。父子关系也需要同步更新。
代码实现 - 左旋：
// 对节点 x 进行左旋
void leftRotate(RedBlackTree* tree, RBTNode* x) {
RBTNode* y = x->right; // 1. 设置 y 为 x 的右孩子
// 2. 将 y 的左子树 beta 变成 x 的右子树
x->right = y->left;
if (y->left != NIL) {
y->left->parent = x;
}
// 3. 将 x 的父节点赋给 y
y->parent = x->parent;
if (x->parent == NIL) { // 如果 x 是根节点
tree->root = y;
} else if (x == x->parent->left) { // 如果 x 是左孩子
x->parent->left = y;
} else { // 如果 x 是右孩子
x->parent->right = y;
}
// 4. 将 x 变成 y 的左孩子
y->left = x;
x->parent = y;
}右旋 (Right Rotation) 与左旋完全对称，这里我们直接给出代码。
代码实现 - 右旋：
// 对节点 y 进行右旋
void rightRotate(RedBlackTree* tree, RBTNode* y) {
RBTNode* x = y->left; // 1. 设置 x 为 y 的左孩子
// 2. 将 x 的右子树 beta 变成 y 的左子树
y->left = x->right;
if (x->right != NIL) {
x->right->parent = y;
}
// 3. 将 y 的父节点赋给 x
x->parent = y->parent;
if (y->parent == NIL) { // 如果 y 是根节点
tree->root = x;
} else if (y == y->parent->left) { // 如果 y 是左孩子
y->parent->left = x;
} else { // 如果 y 是右孩子
y->parent->right = x;
}
// 4. 将 y 变成 x 的右孩子
x->right = y;
y->parent = x;
}有了旋转这个强大的工具，我们就可以在不破坏BST性质的前提下，任意调整树的局部结构了。
🔎 新插入的节点应该是什么颜色？
红黑树首先是一棵二叉搜索树。所以，插入一个新节点的第一步，就是完全按照二叉搜索树的规则，找到它应该在的叶子位置，然后把它放进去。
我们有两个选择：黑色或红色。
选择1️⃣：新节点 = 黑色
根据规则5（从任一节点到其叶子的所有路径包含相同数目的黑色节点），我们新插入的这条路径上，凭空多了一个黑色节点。这就立刻破坏了规则5！
为了修复它，你需要进行非常复杂的调整，因为⚠️你改变了整棵树的“黑高 (Black-Height)”。这太麻烦了。
为什么插入黑色节点困难？
为了回答这个问题，我们需要一棵稍微复杂一点、层数足够多的合法红黑树作为“实验田”。
我们的实验田（一棵合法的4层红黑树）
规则检查: 根是黑；无红-红；所有路径（从根到NIL叶子）黑高均为3 (例如 30(B)->15(B)->10(R)->NIL(B) 这条路径上有3个黑节点: 30, 15, NIL)。
30(B)
/ \
15(B) 50(B)
/ \ / \
10(R) 20(R) 40(R) 60(R)
/ / \ /
5(B) 18(B) 25(B) 55(B)👉 假设我们插入一个 黑色 节点 19(B)
按BST规则找到位置:
19会成为18(B)的右孩子。插入节点: 我们将
19(B)插入。
30(B)
/ \
15(B) 50(B)
/ \ / \
10(R) 20(R) 40(R) 60(R)
/ / \ /
5(B) 18(B) 25(B) 55(B)
\
19(B) <-- 新插入的黑色节点我们破坏了哪个核心规则？👉规则5：从任一节点到其叶子的所有路径必须有相同的黑高。
具体来看，以 18(B) 为起点：
到它的左侧
NIL叶子路径，黑高是1 (NIL(B)本身)。到它的右侧新路径，经过了
19(B)，黑高是2 (19(B)+NIL(B))。
这个局部的不平衡，导致了⚠️全局的不平衡。从根节点 30(B) 出发，到达 19(B) 下方 NIL 叶子的路径，其黑高达到了4，而其他所有路径的黑高仍然是3。
我们怎么办？我们多了一个“黑色单位”的“重量”。
方法1：把这个黑色“甩掉”？ 我们可以把
19(B)变成红色。但这违背了我们“插入黑色节点”的假设。方法2：给所有其他路径都“增加”一个黑色单位？ 这意味着我们需要对树进行大规模的重构和重新着色，影响范围可能波及整棵树，操作极其复杂。
比如，我们需要在
18(B)的兄弟路径（即25(B)这边）也增加一个黑色节点，这又会引发新的不平衡。
插入黑色节点直接破坏了最根本的、全局性的黑高规则。修复它就像一个牵一发而动全身的大手术，没有简单、局部的修复方法。
事实上，红黑树的“删除”操作之所以复杂，就是因为它会产生“双重黑色”节点（double black），这和我们现在面临的“多了一个黑色”的困境是同一种性质的难题。
选择2️⃣：新节点 = 红色
对规则5有影响吗？没有❌。因为路径的黑高没有变。
可能会破坏什么规则？可能会破坏规则4（红色节点的子节点必须是黑色）。如果新插入的红色节点的父节点恰好也是红色的，我们就得到了“红-红”相邻的情况。
如果这是树的第一个节点，我们把它涂成红色，它就成了根节点，这会破坏规则2（根节点是黑色）。
(R)10
/ \
(R)5 NIL
/ \
NIL NIL
初始：插入 10
(R)10 → 修正后 → (B)10
把新节点涂成红色是更明智的选择。因为它最多只会破坏规则2或规则4，而不会破坏最根本的规则5。修复“红-红”相邻的问题，通常是局部的，比修复整个树的黑高要简单得多。
让我们接着刚才的红黑树，插入 21(R)，它会成为 20(R) 的右孩子。
30(B)
/ \
15(B) 50(B)
/ \ / \
10(R) 20(R) 40(R) 60(R)
/ \
18(B) 21(R) <-- 新插入，与父节点20(R)冲突修复的优势:
问题是局部的：冲突只发生在
z(21)、p(20)和g(15)这个小范围内。树的其他大部分，比如右子树50(B)那边，完全不受影响。有明确的模式可以处理: 我们只需要检查叔叔节点
u(10)的颜色。u(10)是红色。这是一个清晰的 Case 1: 叔叔为红色 的情况。修复路径是线性的: 我们的修复方法是“颜色翻转，问题上移”。我们将
p(20)和u(10)变黑，g(15)变红。然后把g(15)当作新的问题节点向上追溯。这个修复过程始终沿着一条从下到上的路径进行，不会“横向”影响其他分支。
代码实现 - 插入新节点
首先，我们需要一个创建新节点的辅助函数。
RBTNode* createNode(int key) {
RBTNode* node = new RBTNode;
node->key = key;
node->color = RED; // 关键：新节点默认为红色
node->left = NIL;
node->right = NIL;
node->parent = NIL; // 暂时设为NIL，插入后会更新
return node;
}现在是插入的主函数。它会先像普通BST一样插入节点，然后调用一个 insertFixup 函数来修复可能被破坏的规则。
// 插入函数
void insert(RedBlackTree* tree, int key) {
RBTNode* z = createNode(key); // z 是要插入的新节点
RBTNode* y = NIL; // y 将是 z 的父节点
RBTNode* x = tree->root; // 从根节点开始查找插入位置
// 1. 按照BST规则找到插入位置
while (x != NIL) {
y = x;
if (z->key < x->key) {
x = x->left;
} else {
x = x->right;
}
}
z->parent = y; // 2. 链接父节点
if (y == NIL) { // 如果树是空的
tree->root = z;
} else if (z->key < y->key) {
y->left = z;
} else {
y->right = z;
}
// 3. 插入完成，调用修复函数
insertFixup(tree, z);
}修复“红-红”问题
现在，我们插入了一个红色节点 z。如果它的父节点 p 是黑色的，那么万事大吉，所有规则都满足，什么都不用做。
真正的挑战在于 p 也是红色的时候。此时我们违反了规则4。
z是红色。z->parent(记为p) 是红色。p->parent(记为g, 祖父节点) 必然是黑色。为什么？因为在插入z之前，这棵树是满足红黑树所有性质的，所以不可能存在“红-红”相邻，因此红色的p的父节点g必须是黑色。
我们的修复策略，完全取决于叔叔节点 (Uncle Node) 的颜色。叔叔节点 u 是 p 的兄弟节点。
Case 1: 叔叔节点 u 是红色
g (BLACK)
/ \
p(RED) u(RED)
/
z(RED)祖父节点 g 是黑的，但它的两个子节点 p 和 u 都是红的。我们新来的 z 也是红的，挂在 p 下面。
假设树原来是这样，我们要插入 z=15(R)。
40(B)
/ \
g(30(B)) 50(B)
/ \
p(20(R)) u(35(R))
/
15(R)插入
z=15(R)，它成为p(20)的左孩子 (为了简化，假设是左孩子)。z(15)和p(20)出现了“红-红”冲突。
📈 当下我们的困境与目标：
根本矛盾: 违反了规则4（不能有连续的红色节点）。
根本约束: 绝对不能违反规则5（黑高不变）。这是红黑树的基石，对它的任何改动都必须是全局性的、非常小心的。
我们的工具: 变色 (Recoloring) 和 旋转 (Rotation)。
1️⃣ 先考虑旋转行不行？
旋转是一个“大手术”，它会改变树的结构。我们看看当前结构有什么问题。g(30) 下面挂着 p(20) 和 u(35)。这个结构本身是平衡的。冲突点 z 在 p 的下面。
如果我们对 g 进行右旋，那么 p 会上位，g 会成为 p 的右孩子，u 怎么办？
u 要挂到 g 的下面。整个结构发生了剧变。这似乎是“杀鸡用牛刀”。有没有更温和的、代价更小的操作？
2️⃣ 再来考虑变色。
变色是“微创手术”，只改变属性，不改变结构。我们能不能只通过变色来解决问题？
分析当前颜色分布:
g(祖父) 是黑色。p(父亲) 和u(叔叔) 都是红色。这形成了一个
BLACK -> (RED, RED)的局部模式。
💡洞察 (The Insight)：
从 g 的父节点（这里是40）看下来，无论是走左边经过 g->p，还是走右边经过 g->u，黑高是多少？
黑高只计算黑色节点。所以从 40 的视角看，经过 g 这个子树，黑高贡献了1（g 本身）。p 和 u 是红色的，不贡献黑高。
40(B)
/ \
g(30(B)) 50(B)
/ \
p(20(R)) u(35(R))
/
15(R)我们现在有一个“黑”的祖父，带着两个“红”的儿子。我们能不能把这个颜色模式反转一下？变成一个“红”的祖父，带着两个“黑”的儿子？
操作:
将
p和u的颜色变为黑色。将
g的颜色变为红色。
g (RED)
/ \
p(BLACK) u(BLACK)
/
z(RED)对规则4（红-红冲突）的影响：
p变成了黑色，所以p(B)和z(R)不再冲突。局部问题解决了！
对规则5（黑高）的影响：
从树根
40(B)往下看，任何经过30这个节点的路径，在操作前，黑高贡献是count_black(30)= 1。在操作后，
g(30)变成了红色，它自己不贡献黑高了。但是，它的两个儿子p和u都变成了黑色。所以任何路径，无论是经过p还是u，黑高贡献依然是1 (count_black(p)或count_black(u))。
对于树的上层部分来说，g(30) 这个子树的整体黑高特性没有改变！我们用一个📊颜色翻转，在没有破坏黑高平衡的前提下，解决了局部的红-红冲突。这是一个极其精妙的、代价极小的操作。
40(B)
/ \
g(30(R)) 50(B) <-- g 变红
/ \
p(20(B)) u(35(B)) <-- p, u 变黑
/
z(15(R)) <-- z, p 之间已无冲突新的问题——问题向上传递
❓我们把 g(30) 染成了红色。现在 g(30) 的父节点是 40(B)，是黑色的，所以没问题。但是如果 40 恰好是红色的呢？那我们不就在 g(30) 和它的父节点 40 之间制造了一个新的“红-红”冲突吗？
这恰恰是这个策略的核心：我们并没有彻底“消灭”问题，而是把问题**“推”上去了两层**。原来的问题在
z和p之间，现在潜在的问题移动到了g和g的父节点之间。
因为问题在向着树的根节点移动。我们只需要把 g 当作新的 z，然后重复整个修复逻辑（检查新z的父节点的颜色，再看新z的叔叔的颜色...）。
问题要么在中间被一个黑色的叔叔通过旋转解决掉，要么最终被推到根节点。如果根节点最后变成了红色，我们只需在修复的最后加一条指令 root->color = BLACK，强制其变黑。
整棵树的黑高会因此加1，但因为所有路径都加1，所以规则5依然成立。
✅当叔叔是红色时，我们之所以选择“颜色翻转”而不是“旋转”，是因为：
代价最小: 它不改变树的结构。
保持黑高: 它精妙地维持了对上层树的黑高不变性。
有效传递问题: 它虽然不能一次性解决问题，但能保证将问题“向上推”，最终总能得到解决。这是一个典型的“分而治之”和“递归”思想的体现。
Case 2: 叔叔节点 u 是黑色 (或NIL)
我们先回顾一下“叔叔为红”时的解决方案：颜色翻转。
这个方案之所以可行，是因为当时 g(B) -> (p(R), u(R)) 的颜色分布是对称的。我们可以把颜色模式翻转为 g(R) -> (p(B), u(B))，并且不会破坏黑高。
现在，“叔叔为黑”时，颜色分布是不对称的：g(B) -> (p(R), u(B))。
第一性推导：
矛盾：“红-红”冲突发生在
p(R) -> z(R)。约束：我们必须维持规则5（黑高平衡）。
尝试颜色翻转：如果我们像之前一样，简单地把
p变黑，g变红，会发生什么？
40(B)
/ \
g(30(R)) 50(B)
/ \
p(20(B)) u(35(R))
/
15(R)在
p这条路径上，黑高增加了1（因为p从红变黑，而g从黑变红，一增一减，但p在g下面，所以路径整体黑高净增1）。
👉结果：两条路径的黑高不再相等，规则5被严重破坏！
颜色不对称，导致简单的颜色翻转方案失效。我们必须采取更强硬的手段来重新平衡树，这个手段就是旋转 (Rotation)。旋转可以改变树的物理结构，让我们有机会重新分配节点和颜色，以同时满足规则4和规则5。
为什么旋转时必须区分“直线”和“三角”？
既然确定了要旋转，下一个问题就是：在哪旋转？怎么转？ 我们的目标是通过旋转，解决 g -> p -> z 这条路径上“红色过多”导致的结构性失衡。最理想的操作，是在祖父节点 g 处进行一次旋转。
现在，我们来分析 z, p, g 的两种几何排列。为了讲解清晰，我们只讨论 p 是 g 的左孩子的情况（右孩子的情况完全对称）。
Subcase 2.1: “直线”情况 (Line)
这是我们的理想模型：z 是 p 的外侧子节点（比如 p 是 g 的左孩子，z 也是 p 的左孩子）。
g(BLACK)
/ \
p(RED) u(BLACK)
/
z(RED)现在 g, p, z 在一条直线上，并且这条路径上有两个连续的红色节点。这导致了结构性失衡。
操作:
对祖父节点
g进行一次旋转（上图是左侧直线，所以对g右旋）。旋转后，
p上位，成了这个子树的新根。将新根
p涂成黑色。将被换下来的
g涂成红色。
p(R)
/ \
z(R) g(B)
/ \
b u(B) (b是p原来的右子树beta)这个结构看起来平衡多了！但是颜色不对，p 和 z 仍然是红-红。
配合颜色调整:
把新的根节点
p涂成黑色。—— 这就解决了红-红冲突。把下沉的
g涂成红色。—— 这是为了补偿p变黑所带来的黑高变化，维持整棵子树对外的黑高不变。
p(B)
/ \
z(R) g(R)
/ \
b u(B)对于“直线”情况，“一次旋转 + 两次变色” 可以完美解决问题。
Subcase 2.2: “三角”情况 (Triangle)
z 是 p 的内侧子节点（比如 p 是 g 的左孩子，z 是 p 的右孩子）。
g(BLACK)
/ \
p(RED) u(BLACK)
\
z(RED)这是一个“Z”字形或“三角”结构。如果我们不加区分，直接对 g 进行右旋，会发生什么？
p上位。g下沉成为p的右孩子。z怎么办？它仍然是p的右孩子。但p的右孩子位置已经被g占了！
p(R)
/ \
? g(B)
/ \
z(R) u(B)这个结构一团糟。p 和 z 仍然是红-红（虽然不直接相连了），并且树的平衡性更差了。
因此，直接在 g 处旋转，对于“三角”情况是无效的。
真正的解决方案：“化三角为直线”
💡“三角”之所以麻烦，就是因为
g-p-z之间有个“拐角”。我们能不能先把这个“拐角”捋直？对
p进行一次与其所在方向相反的旋转（上图是p在左，z在右，所以对p左旋）。旋转后，z上位成了p的父节点。这个操作会把“三角”情况，完美地转换成下面的“直线”情况。此时，新的
z其实是原来的p。
模拟旋转:
z会上位，成为p的父节点。p会下沉，成为z的左孩子。
g(B)
/ \
z(R) u(B)
/
p(R)快看！g -> z -> p 现在是什么形态？它变成了一个完美的“直线”情况！
我们已经把棘手的“三角”问题，转化成了我们已经知道如何解决的“直线”问题。接下来，我们只需对这个新的“直线”形态，执行上一节的解决方案即可。
// ** CASE 2: 叔叔节点 u 是黑色 **
else {
// * Subcase 2.1: 三角形情况 (z 是父节点的内侧孩子) *
// 代码 `z == z->parent->right` 就是在问：“z 是 p 的右孩子吗？”
// 如果是，那就说明是 g(左)-p(右) 的三角形态。
if (z == z->parent->right) {
// 我们需要把这个三角“捋直”。
// 方法是：以 p 为轴进行左旋。
z = z->parent; // 1. 先将焦点 z 暂时上移到 p。
leftRotate(tree, z); // 2. 对 p (现在 z 指向它) 进行左旋。
// 旋转后，原来的 z 上位，原来的 p 下沉。
// 树的结构已经从“三角”变成了“直线”，
// 但我们关注的“引发问题的节点”现在是新的 z (即原来的 p)。
// 代码会自然地进入下面的“直线”处理逻辑。
}
// * Subcase 2.2: 直线情况 (z 是父节点的外侧孩子) *
// 无论是原始的直线情况，还是由三角转化来的直线情况，都会执行这里的代码。
// 1. 颜色调整：将 p 变黑，g 变红。
// 这是为了在旋转后，既能解决红-红冲突，又能维持子树对外的黑高不变。
z->parent->color = BLACK;
z->parent->parent->color = RED;
// 2. 结构调整：在 g 处进行右旋。
// 这是解决结构失衡的决定性一步。
rightRotate(tree, z->parent->parent);
}总结：我们必须区分“直线”和“三角”，因为：
“直线”是可直接处理的理想形态。
“三角”是需要预处理的非理想形态。
处理“三角”的第一步，就是通过一次局部旋转，将其转化为“直线”。
保证根节点是黑色
在 Case 1 的循环中，我们可能会一路把红色推到根节点，导致根是红色的。
所以，在整个 insertFixup 函数的最后，我们必须强制执行规则2：tree->root->color = BLACK。
这可能会让整棵树的黑高增加1，但是因为所有路径都增加了1，所以规则5依然成立。
insertFixup 的完整代码实现
void insertFixup(RedBlackTree* tree, RBTNode* z) {
// 只要父节点是红色，就需要修复
while (z->parent->color == RED) {
// ---- 父节点是祖父节点的左孩子 ----
if (z->parent == z->parent->parent->left) {
RBTNode* u = z->parent->parent->right; // u 是叔叔节点
// ** Case 1: 叔叔是红色 **
if (u->color == RED) {
z->parent->color = BLACK; // p 变黑
u->color = BLACK; // u 变黑
z->parent->parent->color = RED; // g 变红
z = z->parent->parent; // 将 z 指向 g，继续向上检查
}
// ** Case 2: 叔叔是黑色 **
else {
// * Subcase 2.1: 三角情况 *
if (z == z->parent->right) {
z = z->parent; // z 指向 p
leftRotate(tree, z); // 对 p 左旋，变为直线情况
}
// * Subcase 2.2: 直线情况 *
z->parent->color = BLACK; // p 变黑
z->parent->parent->color = RED; // g 变红
rightRotate(tree, z->parent->parent); // 对 g 右旋
}
}
// ---- 父节点是祖父节点的右孩子 (与上面对称) ----
else {
RBTNode* u = z->parent->parent->left; // u 是叔叔节点
// ** Case 1: 叔叔是红色 **
if (u->color == RED) {
z->parent->color = BLACK;
u->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
// ** Case 2: 叔叔是黑色 **
else {
// * Subcase 2.1: 三角情况 *
if (z == z->parent->left) {
z = z->parent;
rightRotate(tree, z);
}
// * Subcase 2.2: 直线情况 *
z->parent->color = BLACK;
z->parent->parent->color = RED;
leftRotate(tree, z->parent->parent);
}
}
}
// 循环结束后，确保根节点是黑色
tree->root->color = BLACK;
}