C++如何实现一个简单的红黑树（Red-Black Tree）插入算法-C++-PHP中文网

红黑树插入前必须满足五条性质：1.节点非红即黑；2.根为黑；3.空叶子为黑；4.红节点子节点必黑；5.任一节点到各叶子的黑节点数相同。

c++如何实现一个简单的红黑树（red-black tree）插入算法

红黑树插入前必须满足的5条性质

红黑树不是随便染色就能工作的。插入新节点后，必须保证以下五条性质全部成立，否则后续查找、删除都会出错：
1. 每个节点是红色或黑色；
2. 根节点是黑色；
3. 所有叶子（nullptr）是黑色；
4. 红色节点的两个子节点都必须是黑色（即不能有两个连续的红节点）；
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑节点（黑高一致）。

实际编码中，第3条和第5条最难靠直觉维护——尤其第5条，它决定了为什么每次插入后都要做「变色 + 旋转」组合操作，而不是只改颜色。

`insert` 后必须调用 `fixInsert` 来恢复性质

标准做法是：先按二叉搜索树规则插入（新节点默认涂红），再立即调用修复函数。不这么做，插入后大概率违反性质4（出现父子同红）。

关键点：
• 新节点设为红色，是为了尽量不破坏性质5（黑高）；
• 但可能违反性质4，所以要向上检查并修复；
• 修复过程只涉及当前节点、父节点、叔节点、祖父节点这四个角色，不需要全局遍历。

示例片段（简化版逻辑）：

void insert(Node* z) {
    // BST 插入逻辑...
    z->color = RED;
    fixInsert(z);
}
<p>void fixInsert(Node<em> z) {
while (z != root && z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
Node</em> y = z->parent->parent->right; // 叔节点
if (y && y->color == RED) {         // 情况1：叔红 → 变色即可
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {                            // 情况2/3：叔黑 → 需旋转
if (z == z->parent->right) {
z = z->parent;
rotateLeft(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rotateRight(z->parent->parent);
}
} else {
// 对称处理（镜像逻辑）
}
}
root->color = BLACK; // 性质2兜底
}</p>

旋转函数必须严格区分 `rotateLeft` 和 `rotateRight` 的指针更新顺序

写错旋转最容易导致指针悬空或循环引用。核心原则：旋转只改变三个节点的父子关系（以 rotateLeft(x) 为例）：
• x 原来的右孩子 y 成为新子树根；
• y 的左孩子变成 x 的右孩子；
• x 变成 y 的左孩子。

C函数速查手册（CHM版）

下载

漏掉任意一步，树结构就损坏了。常见错误包括：
• 忘记更新 y->left->parent（当 y->left 非空时）；
• 忘记更新 x->parent 指向 y；
• 在更新过程中过早覆盖了后续要用的指针（比如先改 x->right，再取 x->right->left 就错了）。

安全写法是把所有待更新的指针先缓存，最后统一赋值：

void rotateLeft(Node* x) {
    Node* y = x->right;
    x->right = y->left;
    if (y->left != nullptr) y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == nullptr) root = y;
    else if (x == x->parent->left) x->parent->left = y;
    else x->parent->right = y;
    y->left = x;
    x->parent = y;
}