1红黑树（三）自顶向下插入
21. 前提条件
3
4自底向上插入是：
5
6先插到底
7再往上修
8
9自顶向下插入是：
10
11一边往下找插入位置
12一边提前调整
13
14目的：
15
16尽量避免插入后再一路回溯修复
17
18所以它叫：
19
20Top-Down Insertion
212. 核心思想
22
23自顶向下红黑树的核心是：
24
25向下搜索时，遇到“两个孩子都是红色”的节点，就提前变色
26
27这种节点长这样：
28
29 G(B)
30 / \
31 L(R) R(R)
32
33这相当于一个“临时的 4-节点”。
34
35处理方法：
36
37G 变红
38L 变黑
39R 变黑
40
41变成：
42
43 G(R)
44 / \
45 L(B) R(B)
46
47这叫：
48
49颜色翻转 / 拆 4-节点
503. 为什么要提前拆？
51
52因为如果不拆，等新节点插到底之后，可能会出现复杂的红红冲突。
53
54自顶向下的想法是：
55
56我还没插到底，
57但我提前把容易出问题的结构拆开。
58
59这样插入到底时，通常局部修一下就够了。
60
614. 和 2-3-4 树的关系
62
63红黑树其实可以看成：
64
652-3-4 树的二叉树表示
66
67简单理解：
68
69黑节点 + 红孩子
70可以看成一个多叉节点
71
72例如：
73
74 10(B)
75 \
76 20(R)
77
78可以理解成一个 3-节点：
79
80[10,20]
81
82如果一个黑节点有两个红孩子：
83
84 20(B)
85 / \
86 10(R) 30(R)
87
88可以理解成一个 4-节点：
89
90[10,20,30]
91
92自顶向下插入时，遇到这种 4-节点，就提前拆开。
93
945. 自顶向下基本流程
95
96插入一个新值 x：
97
98从根开始往下找插入位置
99
100while 当前节点不为空：
101
102 如果当前节点两个孩子都是红色：
103 颜色翻转
104 如果因此出现红红冲突：
105 旋转修复
106
107 根据 BST 规则往左或往右走
108
109最后插入新红节点
110
111根染黑
1126. 颜色翻转例子
113
114原来：
115
116 20(B)
117 / \
118 10(R) 30(R)
119
120向下经过 20 时发现：
121
122左右孩子都是红色
123
124于是翻转：
125
126 20(R)
127 / \
128 10(B) 30(B)
129
130如果 20 的父亲是黑色，那没事。
131
132如果 20 的父亲是红色，就出现：
133
134红父亲
135 ↓
136红20
137
138那就要旋转修复。
139
1407. 和自底向上的区别
141项目 自底向上 自顶向下
142调整时机 插入后往上修 往下找时提前修
143核心操作 看叔叔颜色 提前拆 4-节点
144是否回溯 需要 尽量不需要
145理解难度 更直观 更抽象
146
Rendered Preview
红黑树（三）自顶向下插入
- 前提条件
自底向上插入是：
先插到底
再往上修
自顶向下插入是：
一边往下找插入位置
一边提前调整
目的：
尽量避免插入后再一路回溯修复
所以它叫：
Top-Down Insertion
2. 核心思想
自顶向下红黑树的核心是：
向下搜索时，遇到“两个孩子都是红色”的节点，就提前变色
这种节点长这样：
G(B)
/ \
L(R) R(R)
这相当于一个“临时的 4-节点”。
处理方法：
G 变红
L 变黑
R 变黑
变成：
G(R)
/ \
L(B) R(B)
这叫：
颜色翻转 / 拆 4-节点
3. 为什么要提前拆？
因为如果不拆，等新节点插到底之后，可能会出现复杂的红红冲突。
自顶向下的想法是：
我还没插到底，
但我提前把容易出问题的结构拆开。
这样插入到底时，通常局部修一下就够了。
- 和 2-3-4 树的关系
红黑树其实可以看成：
2-3-4 树的二叉树表示
简单理解：
黑节点 + 红孩子
可以看成一个多叉节点
例如：
10(B)
\
20(R)
可以理解成一个 3-节点：
[10,20]
如果一个黑节点有两个红孩子：
20(B)
/ \
10(R) 30(R)
可以理解成一个 4-节点：
[10,20,30]
自顶向下插入时，遇到这种 4-节点，就提前拆开。
- 自顶向下基本流程
插入一个新值 x：
从根开始往下找插入位置
while 当前节点不为空：
如果当前节点两个孩子都是红色：
颜色翻转
如果因此出现红红冲突：
旋转修复
根据 BST 规则往左或往右走
最后插入新红节点
根染黑
6. 颜色翻转例子
原来：
20(B)
/ \
10(R) 30(R)
向下经过 20 时发现：
左右孩子都是红色
于是翻转：
20(R)
/ \
10(B) 30(B)
如果 20 的父亲是黑色，那没事。
如果 20 的父亲是红色，就出现：
红父亲
↓
红20
那就要旋转修复。
- 和自底向上的区别
项目 自底向上 自顶向下
调整时机 插入后往上修 往下找时提前修
核心操作 看叔叔颜色 提前拆 4-节点
是否回溯 需要 尽量不需要
理解难度 更直观 更抽象