c++oding="utf-8" ?>
红黑树插入后颜色修正的触发条件是新节点父节点为红色；此时需检查叔叔节点颜色并执行变色或旋转，修复中须判空、更新父指针、区分左右场景，最后强制根为黑色。
红黑树插入后颜色修正的触发条件是什么
只有当新插入节点的父节点是红色时，才需要启动颜色修正——因为红黑树的约束之一是“不能有两个连续的红色节点”。此时祖父节点必为黑色（否则插入前树就不合法），而叔叔节点的颜色决定后续走哪条修复路径。
常见错误是忽略 nullptr 指针检查：叔叔节点可能为空，直接访问 uncle->color 会崩溃。务必先判空再取值。
实操建议：
- 统一用
is_red(node)辅助函数（内部处理node == nullptr返回false）代替裸指针访问 - 插入后只对新节点向上修复，不递归处理整棵树；修复结束条件是当前节点变为根或父节点为黑色
- 注意：插入修复最多执行两次旋转，但颜色翻转可能持续向上传播
左旋与右旋必须交换哪些指针才能保持 BST 结构
旋转本质是局部子树重构，核心是维持中序遍历顺序不变。以 rotate_left(x) 为例：x 的右孩子 y 上位为新子树根，x 变成 y 的左孩子；y 原来的左子树（若有）必须挂到 x 的右子树上，否则丢失节点。
容易踩的坑：
- 忘记更新父指针：旋转后
y->parent应设为x->parent，x->parent设为y，且y->left->parent = x（若 y->left 非空） - 没处理子树根节点的父指针变化：若 x 是整棵树的根，旋转后 y 成为新根，其
parent必须置为nullptr - 旋转函数不应假设调用方已校验子节点存在——
rotate_left(x)必须检查x->right != nullptr，否则段错误
为什么修复过程中要区分“父节点是祖父左孩子”和“父节点是祖父右孩子”
红黑树修复不是对称操作，左右场景下旋转方向和颜色调整对象不同。例如：当父节点是祖父的左孩子、叔叔是黑色、且新节点是父节点的右孩子时，需先对父节点左旋，再对祖父右旋；反过来则需先右旋再左旋。
硬编码左右逻辑极易出错。推荐做法：
- 把“父为左/右孩子”映射为布尔标志
is_parent_left_child，用分支统一处理 - 或者将旋转封装为带方向参数的模板函数：
rotate_at(node, direction)，其中direction为LEFT或RIGHT - 不要在修复代码里重复写两套几乎相同的 if-else，维护成本高且易漏改一处
insert_fixup 后为什么还要手动设置根节点为黑色
标准红黑树定义要求根节点必须为黑色。但修复过程只保证“无连续红节点”和“各路径黑高相等”，不保证根色——比如插入第一个节点时它被设为红色，修复中又没被翻黑。
这是最常被忽略的一步。很多开源实现（如早期 libstdc++）也在此栽过坑。
实操建议：
- 在
insert_fixup函数末尾强制执行root->color = BLACK - 注意：如果使用哨兵节点（
NIL），确保root永远不为NIL，否则赋值无效 - 该操作是 O(1) 的，不影响整体复杂度，但缺了就违反红黑树定义，后续查找、删除都会出问题
真正麻烦的不是旋转或变色本身，而是边界指针更新遗漏和空指针解引用。写完一定要用包含单节点、左右斜树、满树、重复键（按你设计的策略处理）的 case 跑一遍，观察 black_height 是否一致、中序遍历是否有序、所有红色节点的孩子是否全黑。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
