红黑树插入后必须先变色再旋转，因为变色可直接消除红-红冲突且维持黑高，而旋转不改颜色；仅当叔父为黑时才需旋转配合变色，且须正确更新parent指针并使用黑色哨兵节点。
红黑树插入后为什么必须先变色再旋转
因为红黑树的平衡依赖两个约束：路径上黑节点数相等（黑高不变），且不能有连续红节点。插入新节点默认为红色，若父节点也是红色，就违反了“红-红不相邻”规则。此时不能直接旋转——旋转不改变颜色，无法消除红-红冲突；必须先尝试变色（比如祖父变红、叔父和父变黑），看是否能恢复性质。只有当叔父是黑色（或为空）时，才需要旋转配合变色来重新分布红节点位置。
常见错误现象：insert 后出现双红父子，但代码跳过变色直接旋转，导致黑高失衡或仍存在红-红边。
- 变色操作只涉及
node->color、parent->color、grandparent->color、uncle->color四个指针，O(1) 开销，应优先执行 - 只有当
uncle == nullptr || uncle->color == BLACK时，才进入旋转分支 - 变色后需向上检查祖父是否破坏了根节点为黑的规则——若
grandparent是根且被设为红色，必须立刻改回黑色
左旋与右旋函数必须更新 parent 指针
很多手写红黑树实现崩在旋转后 parent 指针没重连，导致后续遍历或删除时访问野指针。C++ 中没有自动引用计数的树节点，rotate_left 不仅要改子树结构，还必须显式修正旋转节点及其子节点的 parent 字段。
使用场景：插入后触发 LR/RL 情况（如父为左孩子、新节点为右孩子），需先局部旋转再整体旋转，两次旋转都依赖正确的 parent 链接。
立即学习“C++免费学习笔记（深入）”；
-
rotate_left(Node* x)中，x->right->parent要设为x->parent，而非保持原值 - 若
x是根，旋转后新根的parent必须置为nullptr，否则root->parent非空会干扰is_root()判断 - 旋转后原
x->right成为新子树根，其parent若未更新，后续调用get_grandparent()会返回错误地址
NULL 节点必须统一用黑色哨兵代替
直接用 nullptr 表示空节点会导致颜色判断逻辑爆炸：每次访问 node->left->color 前都要判空，if (uncle && uncle->color == RED) 这类条件极易漏判。C++ 实现中应定义全局静态哨兵节点 nil，其 color = BLACK，所有叶子空位指向它。
性能影响：避免大量空指针检查，使颜色逻辑扁平化；兼容性上，STL 的 std::map 内部也采用类似哨兵设计。
- 声明：
static Node* nil = new Node{BLACK, nullptr, nullptr, nullptr};（构造函数设 color=BLACK，左右子与 parent 全为nil） - 所有新建节点初始化时，
left = right = parent = nil，而非nullptr - 比较颜色可直接写
uncle->color == RED，无需前置非空判断
插入修复循环的终止条件容易写错
标准修复流程是自底向上调整，从新插入节点开始，逐层处理到根。循环终止不是“修复完成”，而是“当前节点为根”或“父节点为黑色”。很多人误写成 while (node != nullptr) 或漏掉对根节点颜色的最终校验。
容易踩的坑：修复中途将某节点设为红色，但它的父是根且为红色——这违反了“根必黑”规则，必须在循环退出后额外检查并修正。
- 正确循环条件：
while (node != root && node->parent->color == RED) - 循环体内必须保证每次迭代后
node向上移动至少一层（如设node = grandparent），否则可能死循环 - 循环结束后，强制
root->color = BLACK，这是兜底操作，不可省略
实际调试时，最常被忽略的是哨兵节点的 parent 字段是否也指向自身或 nil——一旦 nil->parent 是随机值，get_grandparent(nil) 就会解引用非法内存。红黑树的稳定，80% 取决于空节点抽象是否干净。
