insert_fixup用于修复插入后红黑树的局部失衡，仅通过变色和最多三次旋转恢复性质，核心是消除双红冲突、保持黑高一致，需严格更新父子指针并正确处理哨兵nil。
红黑树插入后 insert_fixup 做什么？
它不负责插入节点，只处理插入后违反红黑树性质的局部失衡。核心目标是：让新插入的红色节点 z 不与父节点同为红色，且不破坏黑高一致性和根/叶子节点颜色约束。整个过程仅通过变色（color 切换）和最多三次旋转（left_rotate/right_rotate）完成，时间复杂度 O(log n)。
常见错误现象：插入后树看似平衡，但中序遍历结果正确、却在后续查找或删除时触发断言失败——大概率是 insert_fixup 漏掉了某条路径上的黑高校验，或旋转后未同步更新父子指针的 parent 字段。
- 必须从新节点开始向上迭代，每次循环处理当前节点
z与其父、叔、祖父的关系 - 只有当父节点为红色时才需调整；若父为黑色，直接结束
- 叔节点（
uncle）存在性判断必须用nil（哨兵叶节点）做统一比较，不能只判nullptr
case 1：叔节点为红色时，为什么只变色不旋转？
这是唯一纯靠变色就能恢复局部平衡的情况。父与叔同为红色，说明祖父一定是黑色（否则插入前已违法），此时把父、叔染黑，祖父染红——相当于把“双红冲突”上推一层。只要祖父原本不是根，就可能继续触发上层修复；若是根，则染红后立刻被 root->color = BLACK 修正。
容易踩的坑：
- 变色顺序无关紧要，但必须同时修改父、叔、祖父三者，漏改任一都会导致后续断言失败
- 有些实现误将
uncle == nil当作“无叔节点”，实际红黑树中所有空链接都指向同一nil节点，所以uncle != nil && uncle->color == RED才是 case 1 的完整条件 - 变色后必须把
z更新为祖父（z = z->parent->parent），否则循环无法推进
left_rotate 和 right_rotate 中最容易出错的指针操作
旋转本质是子树结构重挂，关键在于三组父子关系的原子更新：旋转轴节点与其子节点、子节点与其孙节点、原父节点与旋转后新根。漏掉任一链接，树就会断裂或成环。
以 left_rotate(T, x) 为例（x 为左旋轴，y = x->right 为新根）：
-
y->parent = x->parent—— 新根接管原父节点关系，否则上层遍历会跳过整棵子树 - 若
x是根，则T->root = y；否则根据x是左/右孩子更新其父的对应字段 -
x->right = y->left后，必须补y->left->parent = x（若y->left != nil） - 最后才是
y->left = x和x->parent = y
性能影响：旋转本身是 O(1)，但若忘记更新 parent，后续任意一次 successor 或 delete_fixup 都可能因遍历到野指针而崩溃。
为什么删除后的 delete_fixup 比插入更难写对？
因为删除可能引入“双重黑色”节点（概念色，非真实存储），它要求路径黑高比其他路径少 1。修复逻辑要覆盖四种 case，且每个 case 中“当前节点是左/右孩子”和“兄弟节点颜色”形成组合判断，稍有不慎就陷入死循环或漏修。
最常被忽略的细节：
-
delete_fixup的循环条件是x != T->root && x->color == BLACK，但初始传入的x是被删节点的替代者（可能是nil），必须确保它有合法的parent指针 - case 2（兄弟为黑，且两子皆黑）变色后，必须把
x更新为其父，而非继续用原x；否则下轮判断仍满足条件，无限循环 - case 3 和 case 4 都需先对兄弟做一次旋转，再进入 case 4 统一处理——这个“预旋转”步骤极易被跳过或方向写反
真正棘手的不是逻辑分支多，而是调试时无法直接观察“双重黑色”。建议在调试版中给 node 加一个临时字段 double_black，配合日志输出每轮 x 的位置和颜色状态。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
