C++如何实现红黑树节点删除与后继替换及动态平衡调整

红黑树是一种自平衡二叉搜索树，它在插入和删除时通过重新染色与旋转来维持近似平衡。删除操作比插入更复杂，因为移除一个黑色节点会破坏从根到叶子的黑高一致性，必须借助兄弟节点及其子节点的情况进行分类修复。后继节点替换则是删除拥有两个非空子节点时的标准做法，用右子树中最左节点的值覆盖待删节点，再实际删除那个最左节点。

一、红黑树删除的基础结构定义

在 C++ 中实现红黑树，通常先定义节点结构与颜色枚举。每个节点包含键值、颜色、左右子指针与父指针。为了统一处理根节点和空叶子，很多实现引入一个哨兵 NIL 节点，它颜色为黑且不参与数据存储。这样所有真实节点的子节点都不会是空指针，简化了边界判断。

下面给出最基础的节点与树定义。注意 NIL 节点应为全局唯一对象，所有叶子指向它。在删除逻辑中，我们判断某个子是否为空实际上就是判断它是否等于 NIL。这种写法能减少大量的 if (ptr == nullptr) 分支，也让后继替换和平衡调整代码更一致。

#include <iostream>

enum Color { RED, BLACK };

struct Node {
    int key;
    Color color;
    Node* left;
    Node* right;
    Node* parent;
    Node(int k, Color c = RED, Node* l = nullptr, Node* r = nullptr, Node* p = nullptr)
        : key(k), color(c), left(l), right(r), parent(p) {}
};

// 全局哨兵
Node* NIL = new Node(0, BLACK);

class RedBlackTree {
public:
    Node* root;
    RedBlackTree() : root(NIL) {}
    void transplant(Node* u, Node* v);
    Node* minimum(Node* x);
    void deleteNode(Node* z);
    void deleteFixup(Node* x);
    void leftRotate(Node* x);
    void rightRotate(Node* x);
};

二、后继节点查找与替换逻辑

当待删除节点 z 同时拥有左右子树时，不能直接删除 z，否则会破坏二叉搜索树性质。标准做法是找到 z 的右子树中键值最小的节点 y，称之为 z 的后继。将 y 的键值复制到 z，然后实际删除 y。由于 y 是右子树最小节点，它最多只有一个右子节点，删除它只需简单的 transplant 操作。

minimum 函数沿着左指针一直向下即可。transplant 用于把子树 v 替换到 u 的位置，并正确维护父指针。如果 u 是根，则更新 root；否则根据 u 是左孩子还是右孩子来挂接 v。注意 v 的 parent 也要指向 u 的原父节点。这段逻辑和普通二叉搜索树完全一致，与颜色无关。

Node* RedBlackTree::minimum(Node* x) {
    while (x->left != NIL) {
        x = x->left;
    }
    return x;
}

void RedBlackTree::transplant(Node* u, Node* v) {
    if (u->parent == NIL) {
        root = v;
    } else if (u == u->parent->left) {
        u->parent->left = v;
    } else {
        u->parent->right = v;
    }
    v->parent = u->parent;
}

三、删除主流程与黑色高度破坏

deleteNode 首先记录原节点 y 及其颜色。如果 z 只有一个非空子树，直接用该子树替换 z 并删除；如果有两个子树，则找后继 y，记录 y 的颜色，并用 y 的右子替换 y，再把 y 的键值与颜色赋给 z（或直接将 y transplant 到 z 位置）。若 y 的原始颜色为黑，说明删除后少了一个黑节点，必须从 x（替换 y 的节点）开始 fixup。

之所以关注 y 的颜色，是因为只有移除黑节点才会破坏红黑树性质。若 y 是红色，删除它不会影响任何路径的黑高，树依然平衡。反之若 y 为黑，则包含 y 的路径黑节点数少一，需要通过重新染色和旋转在 x 处“借”一个黑色或把红色转黑来补偿。下面代码展示完整的删除分支。

void RedBlackTree::deleteNode(Node* z) {
    Node* y = z;
    Color yOriginalColor = y->color;
    Node* x;
    if (z->left == NIL) {
        x = z->right;
        transplant(z, z->right);
    } else if (z->right == NIL) {
        x = z->left;
        transplant(z, z->left);
    } else {
        y = minimum(z->right);
        yOriginalColor = y->color;
        x = y->right;
        if (y->parent == z) {
            x->parent = y;
        } else {
            transplant(y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        transplant(z, y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;
    }
    delete z;
    if (yOriginalColor == BLACK) {
        deleteFixup(x);
    }
}

四、动态平衡调整 deleteFixup 详解

fixup 过程处理节点 x 处“额外黑”的问题。x 可能是 NIL，但它带着一层虚拟黑色。算法根据 x 是左孩子还是右孩子对称处理，核心在于观察兄弟 w 的颜色以及 w 的子节点颜色。若 w 为红，则通过旋转让 w 变黑、父节点变红，转化为兄弟为黑的情形。

当 w 为黑时，若其两个子节点都是黑，则将 w 染红，并把 x 上移到父节点继续循环；若 w 的右子为黑、左子为红，则右旋 w 并交换颜色，转为右子红的情形；最后若 w 右子为红，则通过左旋父节点、复制父色、将兄弟与侄子染黑来彻底消除额外黑。以下为左孩子情况的完整实现，右孩子只需镜像处理。

void RedBlackTree::deleteFixup(Node* x) {
    while (x != root && x->color == BLACK) {
        if (x == x->parent->left) {
            Node* w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                leftRotate(x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rightRotate(w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                leftRotate(x->parent);
                x = root;
            }
        } else {
            // 镜像处理右孩子情况
            Node* w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rightRotate(x->parent);
                w = x->parent->left;
            }
            if (w->right->color == BLACK && w->left->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    leftRotate(w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rightRotate(x->parent);
                x = root;
            }
        }
    }
    x->color = BLACK;
}

五、旋转操作的辅助实现

左右旋转是平衡调整的基石。左旋转以 x 的右子 y 为支点，将 y 的左子树交给 x 作为右子，再把 x 作为 y 的左子。旋转后必须更新父指针，尤其当 x 为根时更新 root。右旋转完全对称。旋转本身不改变中序遍历顺序，只改变高度与局部颜色分布。

下面是简洁的旋转代码。注意所有涉及 NIL 的指针都要正确赋值 parent，否则 fixup 中访问 w->parent 可能出错。将旋转写成独立函数，能让 deleteFixup 与插入修复共用，减少重复逻辑。

void RedBlackTree::leftRotate(Node* x) {
    Node* y = x->right;
    x->right = y->left;
    if (y->left != NIL) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == NIL) {
        root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

void RedBlackTree::rightRotate(Node* x) {
    Node* y = x->left;
    x->left = y->right;
    if (y->right != NIL) {
        y->right->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == NIL) {
        root = y;
    } else if (x == x->parent->right) {
        x->parent->right = y;
    } else {
        x->parent->left = y;
    }
    y->right = x;
    x->parent = y;
}

六、复杂度与常见误区

红黑树删除的时间复杂度为 O(log n)，其中查找后继与 fixup 最多做两次旋转。很多初学者误以为删除后只要把节点染黑即可，实际上随意染色会破坏路径黑高一致。另一个误区是在 transplant 时忘记维护 NIL 的父指针，导致后续旋转访问空指针。

建议在调试时使用层数打印函数，检查每条根到叶路径的黑色节点数是否相等。只要严格遵循兄弟分类的四种情形，并在循环结束时将根染黑，就能保证删除后树依旧满足红黑性质。理解后继替换与平衡调整的配合，是掌握红黑树工程实现的关键一步。

red_black_treeC++_deleterebalance修改时间：2026-08-05 00:06:56