插入题别背一堆情况，先记：

父红叔红 和 父红叔黑

1. 新结点为什么先染红

新插入结点通常先设为：

[R]

如果直接插黑：

某条路径会立刻多一个黑结点
→ 黑高被破坏

插红最多造成：

红 → 红

这种冲突更容易修。

2. 父亲是黑色

        [B]20
        /
     [R]10

没有违反规则：

父黑 → 直接结束

3. 父亲是红色：先看叔叔

          [B]G
          /
       [R]P
       /
    [R]X

出现红红冲突。

这时先找：

叔叔 U

---

4. 父红，叔红

          [B]G
          /   \
       [R]P   [R]U
       /
    [R]X

处理：

P → 黑
U → 黑
G → 红

变成：

          [R]G
          /   \
       [B]P   [B]U
       /
    [R]X

然后继续向上检查 G。

如果 G 最后成了根：

根重新染黑

大白话：

爸爸叔叔都红
→ 两边一起降温变黑
→ 爷爷变红
→ 问题往上传

---

5. 父红，叔黑

这时一般：

旋转 + 变色

LL

          [B]G
          /
       [R]P
       /
    [R]X

处理：

对 G 右旋
P 变黑
G 变红

RR

    [B]G
        \
        [R]P
            \
            [R]X

处理：

对 G 左旋
P 变黑
G 变红

LR

          [B]G
          /
       [R]P
           \
           [R]X

先把它转成 LL，再按 LL 处理。

RL

    [B]G
        \
        [R]P
        /
     [R]X

先把它转成 RR，再按 RR 处理。

6. 插入固定流程

1. 按二叉排序树规则插入
2. 新结点染红
3. 父黑 → 结束
4. 父红 → 看叔叔
5. 叔红 → 父叔变黑，爷变红，继续向上
6. 叔黑 → 判断 LL/RR/LR/RL，旋转+变色
7. 最后保证根是黑色

7. 一句话口诀

新点先染红
父黑直接停

父红看叔叔：
叔红 → 变色往上传
叔黑 → 看形状做旋转