C++实现红黑树节点的自平衡旋转逻辑 _ 变色与旋转四种情形剖析【源码】

红黑树插入新节点后，一旦父节点是红色，平衡就岌岌可危了。这时候需要根据叔节点的颜色和新增节点的方位，快速判断属于哪种不平衡情形。很多人容易犯一个错误：只盯着插入位置，却忽略了叔节点为空时也算黑色——而这个细节直接决定了是走变色路线还是进入旋转分支。

红黑树插入后四种不平衡情形依叔节点颜色与新节点方位识别：情形1叔红则仅变色；情形2/3叔黑且父左/右子需旋转整形；情形4为镜像；旋转须原子更新三组指针，变色必在旋转后执行以维持性质。

红黑树插入后触发的四种不平衡情形怎么识别

关键不是死记“LL/RR”这类旋转缩写，而是看 parent 和 uncle 的颜色，再结合 node 相对于 parent 的方位。常见的误区是把“插入位置”当成唯一依据，而忽略 uncle 为 nullptr 时也视为黑色——这直接决定走情形1（变色）还是进入旋转分支。

• 情形1：uncle != nullptr && uncle->color == RED → 只变色，不旋转，向上递归检查
• 情形2：uncle == nullptr || uncle->color == BLACK，且 node 是 parent 的左子、parent 是 grandparent 的左子 → 左旋+变色
• 情形3：同上但 node 是右子 → 先对 parent 右旋，转成情形2再处理
• 情形4：镜像情形2/3，发生在右子树 → 对称左旋或先左旋再右旋

rotate_left 和 rotate_right 必须保证子树指针原子更新

旋转不是简单交换父子指针这么简单，必须一次性修正三组连接：原根节点的父指针、子节点的子指针、新根节点的子指针。漏掉任何一环都会导致链表断裂或循环引用。典型的坑点：在 rotate_left 中先改 root->right = child->left，再改 child->left = root，却忘了更新 child->parent 和 root->parent，后续 insert_fixup 就会访问野指针。

• 务必在旋转前保存 child->left（对左旋）或 child->right（对右旋）
• 旋转后立即设置 child->parent = root->parent，否则上层无法定位新根
• 若 root 原为整棵树的根（root->parent == nullptr），旋转后要同步更新 root_ptr

变色逻辑为什么总在旋转之后执行

变色不是独立操作，而是旋转后的配套动作，目的是重置局部路径的黑高并维持根到叶路径的黑节点数一致。提前变色会导致旋转过程中颜色状态错乱——比如情形2中，若先将 parent 染黑、grandparent 染红，再旋转，那么旋转后 grandparent 成为子节点，其红色就直接违反了“红节点子必黑”的规则。正确的顺序永远是：先通过旋转让结构满足“祖父-父-子”共线，再统一调整这三者的颜色。具体标准做法是：

• 情形2/4旋转后：parent->color = BLACK，grandparent->color = RED
• 情形3/4的第一次旋转（如 parent 右旋）不改变颜色，只整形
• 所有情形最终都以 root->color = BLACK 收尾，确保根恒黑

调试时如何快速定位旋转失败的位置

最有效的办法是在每次旋转前后调用一个轻量级验证函数 verify_red_black_property，至少检查三项：root != nullptr && root->color == BLACK、无连续红节点、每条路径黑节点数相等。不要依赖肉眼比对指针地址——在 gdb 中打印 node->left、node->right、node->parent 三者是否构成闭环，比看颜色更可靠。容易被忽略的是空节点处理：红黑树中所有 nullptr 都隐式视为黑色叶子，但你的 Node* 实现里不会真分配内存。所以验证黑高时，递归到底的判据必须是 node == nullptr，而非 node->left == nullptr && node->right == nullptr。一旦发现某次旋转后 verify_red_black_property 失败，立刻在旋转函数入口打日志，输出 node、parent、grandparent 的地址和颜色——90% 的问题出在父指针没更新或空指针解引用。