【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;
            }
        }
    }

    // 最终确保根是黑色，满足性质 2
    root->color = BLACK;
}

✅ 总结五大逻辑结构

红黑树删除修复逻辑解析

🔧 函数签名与入口判断

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 为例）