红黑树插入：修复的艺术
看清一次普通插入为何必定触发修复，掌握三种情形
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
红黑树插入：修复的艺术
看清一次普通插入为何必定触发修复，掌握三种情形
什么是「以曲为直」
上页我们看到修复靠旋转，但旋转明明把节点位置换了，怎么反而让树变平衡？秘密就在「以曲为直」——看起来是绕远路的弯折，实际上是直达平衡的捷径。
铁丝弯一下是为了让两端对齐；树旋转一下是为了让路径重新笔直
左旋 vs 右旋
左右旋像照镜子，但触发条件不同——分不清就会越修越歪。
- 失衡方向：发生在祖父节点的右侧（RR 型 / RL 型修正后）
- 操作动作：右子提为新根，原根降为左子
- 本质：失衡节点的「右孙子」上位
- 失衡方向：发生在祖父节点的左侧（LL 型 / LR 型修正后）
- 操作动作：左子提为新根，原根降为右子
- 本质：失衡节点的「左孙子」上位
双红问题是什么
上一页讲了旋转能调整节点关系，但为何要旋？问题出在「染红」这一步。新节点默认染红，能避免破坏黑高。可万一父节点也是红色，父子撞色，红黑树就违规了——这就是双红问题。
父子层级同红违反「下级不能比上级更显眼」的潜规则，需要重新「调位置」
双红缺陷的两种形态
从双红违规出发, 按 P 在 G 的左右分流成 RR-1 与 RR-2 两条镜像路径, 各自指向修复方向。
插入修复的宏观流程
插入后从下往上检查，遇到双红就按叔叔颜色选策略。
修复策略的决策树
从插入红节点出发，先看父颜色；遇双红再看叔父，按分支选 RR-1 变色或 RR-2 旋转。
RR-1 的处理策略
决策树把我们带到 RR-1：叔父节点也是红色。这是双红里最温和的一种——不旋转，只染色。但染色后祖父变红，可能在他那里再冒双红，所以我们还得把目光继续往上移。
基层红点归位（染黑），异常上报上级（祖父染红），问题跟着上移
RR-1 修复图解
看图理解 RR-1：叔叔为红时只做变色，不改变树结构，修复点上移。
RR-2 的处理策略
RR-1 叔叔是红色，简单换色就完事。RR-2 叔叔是黑色——麻烦来了：新节点和父亲可能扭成「三角」或「直线」两种别扭姿势。继续用「以曲为直」的思路：先掰直，再整体旋转。
中间拧成麻花不能直接翻——先反向拧开拉直，再整体翻过去拧干
RR-2 修复图解
三角→直线→旋转三步走，看 RR-2 如何从折线变直线再变平衡。
RR-1 与 RR-2 对比
何时只需染色、何时必须旋转——插入修复的决策分水岭
- 叔叔节点为红色
- 仅需染色，不改树形
- 违例上移到祖父层
- 叔叔为黑或不存在
- 必须旋转，可能伴随染色
- 本层即可解决
插入修复代码实现
RR-1 染色上提、RR-2 双旋整形——23 行 C++ 覆盖全部边界。
while 盯双红；RR-1 三方染色后 z 上提继续循环；RR-2 内侧先左旋整形，再'父黑祖红+右旋'定型；根强制黑保底。
自测检验
红黑树插入修复双红缺陷时，下列哪种情况应采用「变色」处理（不旋转）？
本节要点回顾
- ✓旋转换色是重画路径,不动插入点
- ✓双红缺陷的本质是黑高被打破
- ✓RR-1 靠局部旋转换色,一步止损
- ✓RR-2 靠递推上溯,把冲突推给祖先
- ✓叔叔颜色是唯一的决策信号
课后思考
先自己琢磨三分钟，再对照参考答案看思路是否一致。
参考答案染色只改变局部颜色，祖父变红、父子变黑，从祖父往上看的子树黑高没变；但祖父变红可能向上触发新的双红，修复可能要循环到根。
参考答案插入 n 个递增键，旋转次数是 O(log n) 量级，比 AVL 树少很多——AVL 要求严格平衡，红黑树容忍适度倾斜，换来更少的旋转代价。
参考答案拿掉后 RR-2 处理需要重写：没有「父红」信号就定位不了失衡点；得另设触发规则，而且单次旋转可能不足以恢复所有不变量。