【C/C++】红黑树插入/删除修复逻辑解析

红黑树插入修复逻辑解析

---

✅ 函数原型

void InsertFixup(Node* &root, Node *node)

• root 是红黑树的根节点的引用（可变）。

• node 是刚插入的新节点。

• 目标：让树重新满足红黑性质，特别是：

  • 不能有两个连续的红色节点（性质 4）
  • 根节点必须为黑色（性质 2）

---

✅ 外层循环条件

while (node != root && node->parent->color == RED)

• 只在当前节点不是根、且父节点是红色时修复。
• 父为红色违反了“红色节点的子节点必须是黑色”的红黑性质。

---

✅ 拿到祖父节点

Node *gp = node->parent->parent;

• 因为父是红色，说明一定不是根节点 → 父节点有祖父节点。
• 所以这里拿 gp 安全。

---

✅ Case 1：父节点是祖父的左孩子

if (node->parent == gp->left)

然后分成两种情况：

① 叔叔节点是红色 → 情况1：颜色翻转（Recolor）

Node *uncle = gp->right;
if (uncle != nullptr && uncle->color == RED) {node->parent->color = BLACK;uncle->color = BLACK;gp->color = RED;node = gp;
}

• 父和叔都是红的，违反红黑规则。
• 做法是将 父和叔变黑，祖父变红，然后将当前节点指向祖父继续上移修复。

② 叔叔节点是黑色或为空 → 情况2或3：旋转 + 颜色修复

else {if (node == node->parent->right) {node = node->parent;RotateLeft(root, node);}node->parent->color = BLACK;gp->color = RED;RotateRight(root, gp);
}

• 如果当前是“右-左”情况（新节点是父的右子），先左旋变成“左-左”结构。
• 然后右旋祖父，父变为子树新根。
• 同时调整颜色，维持红黑规则。

---

✅ Case 2：父节点是祖父的右孩子（对称处理）

else {Node *uncle = gp->left;if (uncle->parent->color == RED) {

❗ 这个地方有个严重 bug：

if (uncle->parent->color == RED)

• 这里不应该访问 uncle->parent->color，应该是：

  if (uncle != nullptr && uncle->color == RED)
  

• 否则当 uncle == nullptr 会导致空指针访问崩溃！

后续逻辑和 Case 1 是对称的：

node->parent->color = BLACK;
uncle->color = BLACK;
gp->color = RED;
node = gp;

或者：

if (node == node->parent->left) {node = node->parent;RotateRight(root, node);
}
node->parent->color = BLACK;
gp->color = RED;
RotateLeft(root, gp);

---

✅ 循环退出后，把根节点设为黑色

root->color = BLACK;

• 保证红黑树“根节点是黑色”这一性质。

---

完整代码示意（带图解）

void InsertFixup(Node* node) {while (node != root && node->parent != nullptr && node->parent->color == RED) {Node* parent = node->parent;Node* grandparent = parent->parent;if (grandparent == nullptr) break;// Case: parent 是 grandparent 的左孩子if (parent == grandparent->left) {Node* uncle = grandparent->right;if (uncle != nullptr && uncle->color == RED) {/*** Case 1: 叔叔是红色，颜色翻转 + 上移**       gp(R)              gp(R) 变红后需要向上递归修复*      /     \     =>     /     \*   pa(R)   unc(R)      pa(B)   unc(B)*    /* node(R)*/parent->color = BLACK;uncle->color = BLACK;grandparent->color = RED;node = grandparent; // 向上传递修复责任} else {if (node == parent->right) {/*** Case 2: node 是“折弯”结构 —— 需要先转成直线**       gp(R)*      /*   pa(R)*      \*     node(R)** 先对 parent 左旋*/node = parent;RotateLeft(node);}/*** Case 3: node 是“直线”结构，右旋 grandparent**       gp(R)                 pa(B)*      /      =>             /    \*   pa(R)                  node(R) gp(R)*   /* node(R)*/node->parent->color = BLACK;   // parent 变为局部根，染黑grandparent->color = RED;RotateRight(grandparent);node = node->parent; // 当前的 parent 是新的局部根，继续修复}} else {// 对称情况：parent 是右孩子Node* uncle = grandparent->left;if (uncle != nullptr && uncle->color == RED) {/*** Case 1（对称）: 叔叔是红色*/parent->color = BLACK;uncle->color = BLACK;grandparent->color = RED;node = grandparent;} else {if (node == parent->left) {/*** Case 2（对称）: 折弯结构，先右旋 parent*/node = parent;RotateRight(node);}/*** Case 3（对称）: 直线结构，左旋 grandparent*/node->parent->color = BLACK;grandparent->color = RED;RotateLeft(grandparent);node = node->parent;}}}// 最终确保根是黑色，满足性质 2root->color = BLACK;
}

✅ 总结五大逻辑结构

条件	动作
父红，叔红	父、叔设黑，祖父设红，往上递归
父红，叔黑，新节点在右	左旋父
父红，叔黑，新节点在左	父设黑，祖父设红，右旋祖父
对称情况（父为右子）	与上面对称处理
根节点必须为黑色	最后强制设 root 为黑

---

红黑树删除修复逻辑解析

🔧 函数签名与入口判断

void DeleteFixup(Node* &root, Node *x, Node *xParent)

• x 是替代被删除节点的位置，可能是 nullptr。
• xParent 是 x 的父节点（尤其在 x == nullptr 时需要）。
• root 是整棵树的引用。

while ((x == nullptr || x->color == BLACK) && x != root)

只要 x 是“多余的黑色”，且不是根，就继续修复。

---

🧩 Case 分支：x 是左子节点（x == xParent->left）

📌 Case 1：w（兄弟）是红色

if (w->color == RED) {w->color = BLACK;xParent->color = RED;RotateLeft(root, xParent);w = xParent->right; // 更新兄弟
}

✅ 通过旋转将兄弟变成黑色，把 Case 1 转换为 Case 2/3/4。

---

📌 Case 2：w 是黑色，且左右孩子都黑（或空）

if ((w->left == nullptr || w->left->color == BLACK)&& (w->right == nullptr || w->right->color == BLACK)) {w->color = RED;x = xParent;xParent = xParent->parent;
}

✅ 兄弟无法提供黑色，继续向上修复。

---

📌 Case 3：w 是黑色，左是红，右是黑

if (w->right == nullptr || w->right->color == BLACK) {if (w->left != nullptr) {w->left->color = BLACK;}w->color = RED;RotateRight(root, w);w = xParent->right;
}

✅ 转换成 Case 4。

---

📌 Case 4：w 是黑色，右是红

w->color = xParent->color;
xParent->color = BLACK;
if (w->right) {w->right->color = BLACK;
}
RotateLeft(root, xParent);
x = root;

✅ 最终修复，黑高恢复，终止循环。

---

🔄 对称分支：x == xParent->right

代码完全对称，只是把“左”和“右”调换：

• 兄弟变为 xParent->left
• 旋转方向反过来：左旋 → 右旋，右旋 → 左旋
• 子节点判断也对称。

---

✅ 最终清理

if (x != nullptr) {x->color = BLACK;
}

避免残留“多余黑色”。

---

🧠 总结逻辑图（以 x == xParent->left 为例）

Case	条件	操作说明
1	w 是红	调色+左旋 → 转为 2/3/4
2	w 黑，左右孩子都黑	兄弟设红，双黑上移
3	w 黑，左红右黑	调色 + 右旋兄弟 → 转为 Case 4
4	w 黑，右红	兄弟右设黑 + 父兄换色 + 左旋 → 修复完成