红黑树的删除操作首先要定位目标节点，若其有两个非空子节点，则需找到中序后继并用它的值与指针替换原节点，再删除后继占用的位置。随后根据被删节点颜色决定是否触发双黑修复，借助旋转与重涂恢复性质。
一、红黑树节点与基本结构
下面给出简化的C++节点定义，使用枚举表示颜色，并通过父指针方便后续旋转与修复。
enum Color { RED, BLACK };
struct Node {
int key;
Color color;
Node* left;
Node* right;
Node* parent;
Node(int k, Color c = RED) : key(k), color(c), left(nullptr), right(nullptr), parent(nullptr) {}
};
二、寻找后继节点
当被删节点拥有左右两棵子树时，其后继为右子树中最小的节点。代码如下：
Node* minimum(Node* x) {
while (x->left != nullptr) {
x = x->left;
}
return x;
}
Node* successor(Node* x) {
if (x->right != nullptr) {
return minimum(x->right);
}
// 若右子树为空则向上找第一个向左拐的祖先
Node* y = x->parent;
while (y != nullptr && x == y->right) {
x = y;
y = y->parent;
}
return y;
}
三、用后继替换被删节点
实际删除函数中，我们先确定真正要摘除的节点y，若目标节点只有一个子节点则用该子节点替换，否则用后继替换。
void transplant(Node*& root, Node* u, Node* v) {
if (u->parent == nullptr) {
root = v;
} else if (u == u->parent->left) {
u->parent->left = v;
} else {
u->parent->right = v;
}
if (v != nullptr) {
v->parent = u->parent;
}
}
void erase(Node*& root, Node* z) {
Node* y = z;
Color yOrigin = y->color;
Node* x = nullptr;
Node* xParent = nullptr;
if (z->left == nullptr) {
x = z->right;
xParent = z->parent;
transplant(root, z, z->right);
} else if (z->right == nullptr) {
x = z->left;
xParent = z->parent;
transplant(root, z, z->left);
} else {
y = minimum(z->right);
yOrigin = y->color;
x = y->right;
xParent = y;
if (y->parent == z) {
if (x != nullptr) x->parent = y;
} else {
transplant(root, y, y->right);
y->right = z->right;
y->right->parent = y;
}
transplant(root, z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
delete z;
if (yOrigin == BLACK) {
// 此处调用双黑修复 fixDoubleBlack(root, x, xParent)
}
}
四、双黑修复的核心思路
若被摘除节点原为黑色，替代它的子节点便承担双黑问题。修复分兄弟为红、兄弟子节点情况等，通过左旋右旋与重涂解决。
- 兄弟为红：将父节点染红、兄弟染黑，向被删侧旋转父节点。
- 兄弟为黑且两子皆黑：兄弟染红，问题上传至父节点。
- 兄弟为黑且内侧子红：先外侧旋转兄弟并交换颜色，转化为下一种情况。
- 兄弟为黑且外侧子红：父兄换色、外侧子染黑，旋转父节点结束修复。
五、小结
掌握后继查找、指针嫁接 transplant 与双黑分类修复，便能在 C++ 中完整实现红黑树删除。建议结合上述代码在本地用随机序列测试，观察每次删除后的黑高是否一致。