红黑树（三）自顶向下插入
1. 前提条件

自底向上插入是：

先插到底
再往上修

自顶向下插入是：

一边往下找插入位置
一边提前调整

目的：

尽量避免插入后再一路回溯修复

所以它叫：

Top-Down Insertion
2. 核心思想

自顶向下红黑树的核心是：

向下搜索时，遇到“两个孩子都是红色”的节点，就提前变色

这种节点长这样：

        G(B)
       /    \
    L(R)    R(R)

这相当于一个“临时的 4-节点”。

处理方法：

G 变红
L 变黑
R 变黑

变成：

        G(R)
       /    \
    L(B)    R(B)

这叫：

颜色翻转 / 拆 4-节点
3. 为什么要提前拆？

因为如果不拆，等新节点插到底之后，可能会出现复杂的红红冲突。

自顶向下的想法是：

我还没插到底，
但我提前把容易出问题的结构拆开。

这样插入到底时，通常局部修一下就够了。

4. 和 2-3-4 树的关系

红黑树其实可以看成：

2-3-4 树的二叉树表示

简单理解：

黑节点 + 红孩子
可以看成一个多叉节点

例如：

    10(B)
      \
      20(R)

可以理解成一个 3-节点：

[10,20]

如果一个黑节点有两个红孩子：

        20(B)
       /    \
    10(R)  30(R)

可以理解成一个 4-节点：

[10,20,30]

自顶向下插入时，遇到这种 4-节点，就提前拆开。

5. 自顶向下基本流程

插入一个新值 x：

从根开始往下找插入位置

while 当前节点不为空：

    如果当前节点两个孩子都是红色：
        颜色翻转
        如果因此出现红红冲突：
            旋转修复

    根据 BST 规则往左或往右走

最后插入新红节点

根染黑
6. 颜色翻转例子

原来：

        20(B)
       /    \
    10(R)  30(R)

向下经过 20 时发现：

左右孩子都是红色

于是翻转：

        20(R)
       /    \
    10(B)  30(B)

如果 20 的父亲是黑色，那没事。

如果 20 的父亲是红色，就出现：

红父亲
  ↓
红20

那就要旋转修复。

7. 和自底向上的区别
项目	自底向上	自顶向下
调整时机	插入后往上修	往下找时提前修
核心操作	看叔叔颜色	提前拆 4-节点
是否回溯	需要	尽量不需要
理解难度	更直观	更抽象