红黑树的节点删除操作需要同时处理二叉查找树的删除逻辑和红黑树的平衡性质维护，整个过程可以分为后继节点查找替换、节点删除、平衡调整三个核心步骤，下面逐一展开分析。
红黑树的基础结构定义
首先需要定义红黑树的节点结构，包含键值、颜色、左右子节点和父节点指针，代码如下：
#include <iostream>
using namespace std;
// 定义红黑树颜色枚举
enum RBColor {
RED,
BLACK
};
// 红黑树节点结构
template <typename T>
struct RBTreeNode {
T key;
RBColor color;
RBTreeNode* left;
RBTreeNode* right;
RBTreeNode* parent;
RBTreeNode(T k, RBColor c = RED, RBTreeNode* l = nullptr, RBTreeNode* r = nullptr, RBTreeNode* p = nullptr)
: key(k), color(c), left(l), right(r), parent(p) {}
};
后继节点查找逻辑
当待删除节点有两个非空子节点时，需要找到它的后继节点来替换其位置。后继节点指的是中序遍历中当前节点的下一个节点，也就是右子树中的最小节点，查找逻辑如下：
// 查找节点的后继节点
template <typename T>
RBTreeNode<T>* findSuccessor(RBTreeNode<T>* node) {
if (node == nullptr || node->right == nullptr) {
return nullptr;
}
// 右子树的最小节点即为后继节点
RBTreeNode<T>* cur = node->right;
while (cur->left != nullptr) {
cur = cur->left;
}
return cur;
}
后继节点替换逻辑
找到后继节点后，需要将后继节点的键值替换到待删除节点中，然后删除后继节点本身。替换过程需要注意处理后继节点的父子节点关系，代码如下：
// 替换节点u为节点v，处理父子关系
template <typename T>
void transplant(RBTreeNode<T>*& root, RBTreeNode<T>* u, RBTreeNode<T>* v) {
if (u->parent == nullptr) {
// u是根节点，直接让v成为新根
root = v;
} else if (u == u->parent->left) {
// u是父节点的左子节点
u->parent->left = v;
} else {
// u是父节点的右子节点
u->parent->right = v;
}
if (v != nullptr) {
// v不为空时更新父节点指针
v->parent = u->parent;
}
}
// 后继节点替换实现
template <typename T>
void replaceWithSuccessor(RBTreeNode<T>*& root, RBTreeNode<T>* node, RBTreeNode<T>* successor) {
// 将后继节点的键值复制到待删除节点
node->key = successor->key;
// 删除后继节点，后继节点最多只有一个右子节点
RBTreeNode<T>* successorChild = successor->right;
transplant(root, successor, successorChild);
}
节点删除核心流程
结合上述两个逻辑，完整的删除流程需要先判断待删除节点的子节点情况，再决定是直接删除还是替换后删除，代码如下：
template <typename T>
void rbTreeDelete(RBTreeNode<T>*& root, RBTreeNode<T>* node) {
if (node == nullptr) {
return;
}
RBTreeNode<T>* toDelete = node;
RBTreeNode<T>* fixNode = nullptr;
RBColor originalColor = toDelete->color;
// 情况1：左子节点为空
if (node->left == nullptr) {
fixNode = node->right;
transplant(root, node, node->right);
}
// 情况2：右子节点为空
else if (node->right == nullptr) {
fixNode = node->left;
transplant(root, node, node->left);
}
// 情况3：左右子节点都不为空，找后继节点替换
else {
toDelete = findSuccessor(node);
originalColor = toDelete->color;
fixNode = toDelete->right;
if (toDelete->parent == node) {
// 后继节点是待删除节点的右子节点
if (fixNode != nullptr) {
fixNode->parent = toDelete;
}
} else {
transplant(root, toDelete, toDelete->right);
toDelete->right = node->right;
toDelete->right->parent = toDelete;
}
transplant(root, node, toDelete);
toDelete->left = node->left;
toDelete->left->parent = toDelete;
toDelete->color = node->color;
}
// 如果删除的节点是黑色，需要修复红黑性质
if (originalColor == BLACK) {
// 此处省略平衡调整代码，调整逻辑需根据fixNode的父节点和兄弟节点情况处理
// 核心是保证每条路径的黑色节点数量一致，无连续的红色节点
}
delete node;
}
删除逻辑的关键注意点
在实现删除逻辑时，需要注意几个核心问题：第一，后继节点的查找必须保证节点有右子树，否则不存在后继节点；第二，替换操作必须同步更新父节点和子节点的指针，避免出现野指针；第三，只有删除黑色节点时才需要触发平衡调整，删除红色节点不会影响红黑树的性质，不需要额外处理。另外，在编写代码时要特别注意指针判空，避免访问空指针导致程序崩溃。
总结
红黑树的节点删除与后继节点替换逻辑虽然复杂，但只要拆解成查找后继、替换节点、删除节点、平衡调整四个步骤，就能逐步理清实现思路。后继节点的替换本质是复用二叉查找树的删除逻辑，而平衡调整则是红黑树特有的部分，需要结合红黑树的五条性质来设计不同场景的处理方案。通过完整的源码实现和逻辑分析，开发者可以更清晰地理解整个删除流程的运作机制，在实际开发中正确实现红黑树的删除功能。