红黑树插入后失衡的四种情形通过叔父节点颜色和当前节点与父节点的左右位置关系识别：叔父为红时属情形1（仅变色）；叔父为黑时，若节点与父同侧则单旋（情形2/4），异侧则双旋（情形3/5）。
红黑树插入后失衡的四种情形怎么识别
红黑树插入新节点后，仅当父节点为红色时才可能破坏性质，此时需从“叔父节点颜色”和“当前节点位置关系”两个维度判断情形。关键不是死记编号，而是看 parent 和 uncle 的颜色 + node 相对于 parent 的左右方位。
实际编码中，先统一用 get_uncle() 获取叔父（可能为空），再分两层判断：
- 若
uncle != nullptr && uncle->color == RED→ 情形1：叔父红 → 只变色，不旋转 - 否则，叔父黑（或空），再看
node和parent是否同侧（比如都是左孩子）→ 同侧则单旋（情形2/4），异侧则双旋（情形3/5）
注意：nullptr 视为黑色，所以“叔父为空”等价于“叔父黑”，直接走旋转分支。
左旋与右旋函数必须保证子树根更新 parent 指针
很多初学者写的 rotate_left() 只改了指针指向，但忘了修正被旋转节点的 parent 字段，导致后续向上回溯时 parent 错乱，平衡失败甚至崩溃。
正确做法（以左旋为例）：
void rotate_left(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;
}
重点检查三处：y->left->parent、x->parent 赋值、以及 y 接入上层的位置更新。漏掉任意一个，insert_fixup() 就会走错路径。
变色操作只在情形1执行，且必须自底向上批量修改
情形1（叔父红）的本质是把局部冲突上推一层：将 parent 和 uncle 染黑，grandparent 染红，然后以 grandparent 为新 node 继续向上修复。这不是一次性的颜色调整，而是一个 while 循环过程。
常见错误包括：
- 只改了当前三层节点颜色，没把
node更新为grandparent，导致循环退出过早 - 没判断
node->parent == nullptr就访问node->parent->color，触发空指针解引用 - 在
node已是根节点时仍尝试染红根 —— 违反红黑树性质，必须强制染黑并 break
因此修复循环的终止条件应为：node != root && node->parent->color == RED，并在循环末尾 node = node->parent。
插入修复函数要处理好根节点强制变黑这个边界
无论经过多少次变色或旋转，最终都要确保根节点是黑色。这个动作不能放在情形判断里，而应在 insert_fixup() 结束后单独执行 —— 因为旋转本身不改变根的颜色，而情形1的上推可能让根变成红色。
所以标准结构是：
void insert_fixup(Node* node) {
while (node != root && node->parent->color == RED) {
// 四种情形分支...
}
root->color = BLACK; // 必须有，且放在这里
}
漏掉这行，或把它塞进某个 if 分支里，都会导致某些插入序列后根为红色，整棵树失效。这是最容易被忽略、也最难调试的点 —— 它不报错，但后续查找/删除行为全乱。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
