红黑树插入后必须调整，因为新节点默认染红会破坏“无连续红节点”和“每路径黑节点数相等”性质；修复需分叔节点红/黑两类情况，涉及变色与左右旋组合，并更新父指针、用哨兵节点简化判空。

红黑树插入后为什么必须调整？

因为直接插入新节点会破坏红黑树的 5 条性质，尤其是「任意路径上黑节点数相同」和「不能有两个连续的红色节点」这两条。新节点默认涂红，虽然不增加黑高，但可能引发 red-red violation（父节点也是红色）。这时候就得靠旋转 + 变色来修复。

• 插入后只有三种情况需要处理：当前节点 z、父节点 z->parent、祖父节点 z->parent->parent 构成的局部结构
• 所有调整都围绕祖父节点展开，且只在父节点为红色时触发（否则无需调整）
• 调整过程不改变黑高，也不引入新 violation，是局部、有限步的

怎么区分 uncle 节点颜色并选择分支？

关键看叔父节点（parent 的兄弟）是否为红色——它决定了是「简单变色」还是「旋转+变色」：

• 如果 uncle != nullptr && uncle->color == RED：执行变色（parent 和 uncle 染黑，grandparent 染红），然后把 z 上移到 grandparent，继续向上检查
• 否则（uncle 是黑色或空）：进入旋转分支，此时需先根据 z 相对于 parent 的位置，以及 parent 相对于 grandparent 的位置，判断是 LL / LR / RR / RL 型
• 注意：nullptr 节点视为黑色，所以 uncle 为空等价于黑色，直接进旋转分支

旋转前为什么要先统一成 LL 或 RR 型？

因为红黑树调整只定义了两种基础旋转（left_rotate 和 right_rotate），而插入可能造成 LR 或 RL 结构（即 z 是 parent 的右孩子，但 parent 是 grandparent 的左孩子）。这种情况下直接旋转会错乱父子关系。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

• 遇到 LR 型：先对 z->parent 调用 left_rotate，把结构转成 LL 型，再对 grandparent 调用 right_rotate
• 遇到 RL 型：先对 z->parent 调用 right_rotate，转成 RR 型，再对 grandparent 调用 left_rotate
• 旋转后必须交换参与节点的颜色（比如旋转后原 parent 成为新子树根，要继承 grandparent 的黑色），否则黑高会变
• 所有旋转函数里，必须更新 parent 指针（尤其是 root 可能变更，要记得改 root 成员）

手写时最容易漏掉的细节有哪些？

• 忘记在旋转后重设 root：如果 grandparent 是原 root，旋转后它变成子节点，新根必须赋给 root
• parent 指针维护错误：比如 left_rotate 中，y->parent 应设为 x->parent，而 x->parent 更新后，若它非空，还得判断 x 是左/右孩子并更新对应指针
• 叔父节点判空不严谨：用 uncle == nullptr 判断黑色没问题，但后续访问 uncle->color 前必须加空指针检查，否则段错误
• 插入后没把 root->color = BLACK：虽然调整过程一般不会让 root 变红，但规范要求 root 永远是黑的，收尾强制设置更安全

边界情况比想象中多，尤其在递归上移或旋转嵌套时，建议每步后用小数据（比如插入 1~5 的序列）手模验证节点颜色和结构。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！