1红黑树（第一章：基础）
21. 前提条件
3
4红黑树（Red-Black Tree）是一种：
5
6 自平衡二叉搜索树（Self-Balancing BST）
7
8它和 AVL 一样：
9
10左子树 < 根 < 右子树
11中序遍历仍然是有序序列
12查找、插入、删除平均都是
13O(log n)
14
15所以：红黑树 = BST + 自动保持平衡
16
17为什么还要发明红黑树？
18
19因为BST：
20
21插入：
22
231
24
252
26
273
28
294
30
315
32
33会变成：
34
351
36 \
37 2
38 \
39 3
40 \
41 4
42 \
43 5
44
45高度：5
46
47查找：O(n)
48
49于是AVL 出来了。
50
51AVL：任何节点：
52
53左右高度差 ≤ 1
54
55非常平衡。
56
57但是：
58
59AVL 的缺点：
60
61插入旋转较多
62
63删除旋转更多
64
65工程上：例如：
66
67Linux 内核
68
69C++ STL(set/map)
70
71更多使用：红黑树
72
73因为宁可稍微高一点，也尽量少旋转。
74
752. 红黑树是什么？
76
77BST+颜色(Color)
78
79每个节点：
80
81除了key，还多了color
82
83例如：
84
85struct TreeNode
86{
87 int key;
88
89 int color;
90
91 struct TreeNode* left;
92
93 struct TreeNode* right;
94
95 struct TreeNode* parent;
96};
97
98颜色只有：
99
100RED
101
102BLACK
103
104例如：
105
106 20(B)
107
108 / \
109
110 10(R) 30(R)
111
112
1133. 红黑树五条性质
114性质一
115
116每个节点不是红色就是黑色
117
118只有：
119
120RED
121
122BLACK
123
124性质二
125
126根节点
127
128必须是黑色
129
130例如：
131
132正确：
133
134 20(B)
135
136错误：
137
138 20(R)
139
140性质三
141所有 NULL
142
143都是黑色
144
145例如：
146
147 20(B)
148
149 /
150
151 10(R)
152
153其实：
154
155真正画出来：
156
157 20(B)
158
159 / \
160
161 10(R) NULL(B)
162
163 / \
164
165 NULL(B) NULL(B)
166
167注意：
168
169NULL
170
171也算：
172
173黑节点
174
175
176性质四
177
178这是最重要的一条。
179
180红节点
181
182不能有红孩子
183
184也就是说：
185
186RED
187
188↓
189
190RED
191
192禁止。
193
194例如：
195
196错误：
197
198 20(B)
199
200 /
201
202 10(R)
203
204 /
205
206 5(R)
207
208因为：
209
210红
211
212↓
213
214红
215
216违反。
217
218所以插入如果出现：
219
220红
221
222↓
223
224红
225
226必须调整
227
228性质五
229
230任何节点：
231
232到所有NULL
233路径黑节点数量必须一样。
234
235例如：
236
237正确：
238
239 20(B)
240
241 / \
242
243 10(R) 30(B)
244
245 / \ / \
246
247 NULL NULL NULL NULL
248
249左边：
250
25120(B)
252
253↓
254
255NULL(B)
256
257黑：2
258
259右边：
260
26120(B)
262
263↓
264
26530(B)
266
267↓
268
269NULL(B)
270
271黑：
272
2733
274
275这棵树其实不满足性质五。
276
277再举一个满足的例子：
278
279 20(B)
280
281 / \
282
283 10(R) 30(R)
284
285 / \ / \
286
287 NULL NULL NULL NULL
288
289左边：
290
29120(B)
292
293↓
294
295NULL(B)
296
297黑：
298
2992
300
301右边：
302
30320(B)
304
305↓
306
307NULL(B)
308
309黑：
310
3112
312
313一样。
314
315所以合法。
316
3174. 什么叫黑高（Black Height）
318
319黑高，定义：
320
321从某节点到所有 NULL
322
323经过黑节点数量。
324
325例如：
326
327 20(B)
328
329 /
330
331 10(R)
332
333从20往下：
334
33520(B)
336
337↓
338
33910(R)
340
341↓
342
343NULL(B)
344
345黑：
346
34720
348
349NULL
350
351=
352
3532
354
355黑高：2
356
3575. 为什么能保持平衡？
358
359AVL保证：左右高度差≤1
360
361所以非常平衡。
362红黑树不是
363
364例如可以：
365
366左边高一点。
367
368但是由于不能连续两个红节点
369
370所以：
371
372最长路径：
373
374最多：
375
376黑
377
378红
379
380黑
381
382红
383
384黑
385
386红
387
388最短可能：
389
390黑
391
392黑
393
394黑
395
396因此最长最多是最短2 倍
397
398红黑树高度≤2log₂(n+1)
399
400所以查找仍然O(logn)
401
4026. 红黑树和 AVL 的区别
403
404
405
406AVL 红黑树
407高度最平衡 近似平衡
408左右高度差≤1 五条颜色规则
409查找最快 查找稍慢
410插入旋转较多 插入旋转较少
411删除最麻烦 删除简单一些
412适合查询 适合插入删除频繁
413
414
415AVL：查找最快。
416
417红黑树：综合性能最好。
418
419
4207. 为什么颜色只有红黑？
421
422颜色其实是一种状态
423
424红表示这一层可以不算高度
425
426黑表示真正增加高度。
427
428所以红节点：只是缓冲
429
430真正限制高度的是黑节点数量。
431
4328. 为什么新插入节点都是红色？
433
434先记结论：
435
436如果插入：黑节点：
437
438例如：20(B)
439
440插10(B)
441
442那么左边：
443
444黑节点立刻增加。
445
446性质五马上坏掉。
447
448如果：插10(R)，黑节点没增加。
449
450更容易调整。
451
452所以新节点默认红色
453
4549. 红黑树整体结构
455
456例如：
457
458 20(B)
459
460 / \
461
462 10(R) 40(R)
463
464 / \ / \
465
466 5(B) 15(B) 30(B) 50(B)
467
468
46910. 总结
470
471红黑树
472
473本质：BST+颜色约束
474
475--------------------------------
476
477五条性质：
478
479① 每个节点非红即黑
480
481② 根必须黑
482
483③ NULL都是黑
484
485④ 红节点不能有红孩子
486
487⑤ 任意路径黑节点数相同
488
489--------------------------------
490
491为什么平衡？
492
493不能连续红
494
495最长路径≤最短路径2倍
496
497高度：
498
499≤2log(n)
500
501--------------------------------
502
503AVL：
504
505更平衡
506
507查询最快
508
509--------------------------------
510
511红黑树：
512
513稍高一点
514
515旋转少
516
517工程最常用
518
519--------------------------------
520
521插入删除
522
523都是为了维护：
524
525第四条
526
527第五条
红黑树（第一章：基础）
- 前提条件
红黑树（Red-Black Tree）是一种：
自平衡二叉搜索树（Self-Balancing BST）
它和 AVL 一样：
左子树 < 根 < 右子树
中序遍历仍然是有序序列
查找、插入、删除平均都是
O(log n)
所以：红黑树 = BST + 自动保持平衡
为什么还要发明红黑树？
因为BST：
插入：
1
2
3
4
5
会变成：
1
2
3
4
5
高度：5
查找：O(n)
于是AVL 出来了。
AVL：任何节点：
左右高度差 ≤ 1
非常平衡。
但是：
AVL 的缺点：
插入旋转较多
删除旋转更多
工程上：例如：
Linux 内核
C++ STL(set/map)
更多使用：红黑树
因为宁可稍微高一点，也尽量少旋转。
- 红黑树是什么？
BST+颜色(Color)
每个节点：
除了key，还多了color
例如：
struct TreeNode
{
int key;
int color;
struct TreeNode* left;
struct TreeNode* right;
struct TreeNode* parent;
};
颜色只有：
RED
BLACK
例如：
20(B)
/ \
10(R) 30(R)
- 红黑树五条性质
性质一
每个节点不是红色就是黑色
只有：
RED
BLACK
性质二
根节点
必须是黑色
例如：
正确：
20(B)
错误：
20(R)
性质三
所有 NULL
都是黑色
例如：
20(B)
/
10(R)
其实：
真正画出来：
20(B)
/ \
10(R) NULL(B)
/ \
NULL(B) NULL(B)
注意：
NULL
也算：
黑节点
性质四
这是最重要的一条。
红节点
不能有红孩子
也就是说：
RED
↓
RED
禁止。
例如：
错误：
20(B)
/
10(R)
/
5(R)
因为：
红
↓
红
违反。
所以插入如果出现：
红
↓
红
必须调整
性质五
任何节点：
到所有NULL
路径黑节点数量必须一样。
例如：
正确：
20(B)
/ \
10(R) 30(B)
/ \ / \
NULL NULL NULL NULL
左边：
20(B)
↓
NULL(B)
黑：2
右边：
20(B)
↓
30(B)
↓
NULL(B)
黑：
3
这棵树其实不满足性质五。
再举一个满足的例子：
20(B)
/ \
10(R) 30(R)
/ \ / \
NULL NULL NULL NULL
左边：
20(B)
↓
NULL(B)
黑：
2
右边：
20(B)
↓
NULL(B)
黑：
2
一样。
所以合法。
- 什么叫黑高（Black Height）
黑高，定义：
从某节点到所有 NULL
经过黑节点数量。
例如：
20(B)
/
10(R)
从20往下：
20(B)
↓
10(R)
↓
NULL(B)
黑：
20
NULL
=
2
黑高：2
- 为什么能保持平衡？
AVL保证：左右高度差≤1
所以非常平衡。
红黑树不是
例如可以：
左边高一点。
但是由于不能连续两个红节点
所以：
最长路径：
最多：
黑
红
黑
红
黑
红
最短可能：
黑
黑
黑
因此最长最多是最短2 倍
红黑树高度≤2log₂(n+1)
所以查找仍然O(logn)
- 红黑树和 AVL 的区别
AVL 红黑树
高度最平衡 近似平衡
左右高度差≤1 五条颜色规则
查找最快 查找稍慢
插入旋转较多 插入旋转较少
删除最麻烦 删除简单一些
适合查询 适合插入删除频繁
AVL：查找最快。
红黑树：综合性能最好。
- 为什么颜色只有红黑？
颜色其实是一种状态
红表示这一层可以不算高度
黑表示真正增加高度。
所以红节点：只是缓冲
真正限制高度的是黑节点数量。
- 为什么新插入节点都是红色？
先记结论：
如果插入：黑节点：
例如：20(B)
插10(B)
那么左边：
黑节点立刻增加。
性质五马上坏掉。
如果：插10(R)，黑节点没增加。
更容易调整。
所以新节点默认红色
- 红黑树整体结构
例如：
20(B)
/ \
10(R) 40(R)
/ \ / \
5(B) 15(B) 30(B) 50(B)
- 总结
红黑树
本质：BST+颜色约束
五条性质：
① 每个节点非红即黑
② 根必须黑
③ NULL都是黑
④ 红节点不能有红孩子
⑤ 任意路径黑节点数相同
为什么平衡？
不能连续红
最长路径≤最短路径2倍
高度：
≤2log(n)
AVL：
更平衡
查询最快
红黑树：
稍高一点
旋转少
工程最常用
插入删除
都是为了维护：
第四条
第五条
