1VL树（平衡二叉查找树）
21. 前提条件
3
4先回忆 BST：
5
6左子树 < 根
7
8右子树 > 根
9
10例如：
11
12 8
13 / \
14 4 10
15 / \ \
16 2 6 12
17
18查找：
19
20O(log n)
21
22很快。
23
24但是 BST 有个问题。
25
26如果插入：
27
281
292
303
314
325
33
34会变成：
35
361
37 \
38 2
39 \
40 3
41 \
42 4
43 \
44 5
45
46已经不是树了。
47
48变成：
49
50链表
51
52查找：
53
54O(n)
55
56退化了。
57
58所以提出：
59
60AVL Tree
612. 核心概念
62
63AVL：
64
65平衡二叉查找树
66
67Balanced Binary Search Tree
68
69AVL首先是BST。
70
71所以仍然满足：
72
73左小右大
74
75同时增加要求：
76
77任何结点
78
79左右子树高度差
80
81不能超过1
82
83例如：
84
85合法：
86
87 4
88 / \
89 2 6
90
91左高度：
92
931
94
95右高度：
96
971
98
99高度差：
100
1010
102
103合法。
104
105再例如：
106
107 4
108 /
109 2
110 /
111 1
112
113左高度：
114
1152
116
117右高度：
118
1190
120
121高度差：
122
1232
124
125不合法。
126
1273. 平衡因子 BF
128
129AVL最重要概念。
130
131定义：
132
133BF
134
135=
136
137左子树高度
138
139-
140
141右子树高度
142
143例如：
144
145 4
146 / \
147 2 6
148
149左右高度：
150
1511
152
1531
154
155所以：
156
157BF = 1-1 = 0
158
159再例如：
160
161 4
162 /
163 2
164
165高度：
166
167左=1
168
169右=0
170
171所以：
172
173BF = 1
174
175AVL允许：
176
177BF=-1
178
179BF=0
180
181BF=1
182
183不允许：
184
185BF=2
186
187BF=-2
1884. AVL为什么快
189
190AVL始终保持：
191
192接近平衡
193
194所以高度不会太大。
195
196BST最坏：
197
198高度=n
199
200AVL：
201
202高度≈log₂n
203
204因此：
205
206查找 O(log n)
207
208插入 O(log n)
209
210删除 O(log n)
2115. AVL什么时候失衡
212
213插入新节点以后。
214
215例如：
216
217插入：
218
21930
22020
22110
222
223得到：
224
225 30
226 /
227 20
228 /
22910
230
231看30：
232
233左高度=2
234
235右高度=0
236
237所以：
238
239BF=2
240
241失衡。
242
243此时需要：
244
245旋转
2466. AVL四种失衡
247
248考试必考。
249
250只有四种。
251
252LL
253 30
254 /
255 20
256 /
257 10
258
259特点：
260
261左孩子的左边插入
262
263口诀：
264
265LL
266
267右旋
268RR
26910
270 \
271 20
272 \
273 30
274
275特点：
276
277右孩子的右边插入
278
279口诀：
280
281RR
282
283左旋
284LR
285 30
286 /
287 10
288 \
289 20
290
291特点：
292
293左孩子的右边插入
294
295口诀：
296
297LR
298
299先左旋
300
301再右旋
302RL
30310
304 \
305 30
306 /
307 20
308
309特点：
310
311右孩子的左边插入
312
313口诀：
314
315RL
316
317先右旋
318
319再左旋
3207. AVL判断口诀
321
322考试最快方法。
323
324发现：
325
326BF=2
327
328说明左边太高
329
330再看：
331
332新增结点
333
334在左孩子左边？
335
336还是左孩子右边？
337
338如果：
339
340左孩子左边
341
342就是：
343
344LL
345
346如果：
347
348左孩子右边
349
350就是：
351
352LR
353
354同理：
355
356BF=-2
357
358说明：
359
360右边太高
361
362看新增结点：
363
364右孩子右边
365
366RR
367
368或者：
369
370右孩子左边
371
372RL
3738. AVL结构体
374
375一般和BST一样。
376
377struct TreeNode
378{
379 int val;
380
381 struct TreeNode* left;
382
383 struct TreeNode* right;
384
385 int height;
386};
387
388新增：
389
390height
391
392记录高度。
393
3949. AVL为什么需要height
395
396因为要算：
397
398BF
399
400而：
401
402BF
403
404=
405
406左高度
407
408-
409
410右高度
411
412所以每个节点都保存：
413
414height
415
416方便计算。
417
41810. 易错点
419易错点1
420
421AVL首先是BST
422
423仍然满足：
424
425左小右大
426
427不要忘。
428
429易错点2
430
431AVL不是完全平衡树
432
433允许：
434
435BF=1
436
437BF=0
438
439BF=-1
440
441不是：
442
443必须相等
444易错点3
445
446失衡只会有四种：
447
448LL
449
450RR
451
452LR
453
454RL
455
456考试看到图先判断类型。
457
458易错点4
459
460双旋转别背反
461
462口诀：
463
464LR
465
466先左后右
467
468RL
469
470先右后左
471AVL总结（考试版）
472AVL树
473
474定义：
475
476平衡二叉查找树
477
478--------------------------------
479
480首先是BST：
481
482左子树 < 根
483
484右子树 > 根
485
486--------------------------------
487
488平衡因子：
489
490BF
491
492=
493
494左高度
495
496-
497
498右高度
499
500--------------------------------
501
502合法：
503
504BF=-1
505
506BF=0
507
508BF=1
509
510--------------------------------
511
512失衡：
513
514BF=2
515
516BF=-2
517
518--------------------------------
519
520四种失衡：
521
522LL
523
524RR
525
526LR
527
528RL
529
530--------------------------------
531
532对应旋转：
533
534LL
535
536右旋
537
538----------------
539
540RR
541
542左旋
543
544----------------
545
546LR
547
548左旋+右旋
549
550----------------
551
552RL
553
554右旋+左旋
555
556--------------------------------
557
558复杂度：
559
560查找 O(log n)
561
562插入 O(log n)
563
564删除 O(log n)
VL树（平衡二叉查找树）
- 前提条件
先回忆 BST：
左子树 < 根
右子树 > 根
例如：
8
/ \
4 10
/ \ \
2 6 12
查找：
O(log n)
很快。
但是 BST 有个问题。
如果插入：
1
2
3
4
5
会变成：
1
2
3
4
5
已经不是树了。
变成：
链表
查找：
O(n)
退化了。
所以提出：
AVL Tree
2. 核心概念
AVL：
平衡二叉查找树
Balanced Binary Search Tree
AVL首先是BST。
所以仍然满足：
左小右大
同时增加要求：
任何结点
左右子树高度差
不能超过1
例如：
合法：
4
/ \
2 6
左高度：
1
右高度：
1
高度差：
0
合法。
再例如：
4
/
2
/
1
左高度：
2
右高度：
0
高度差：
2
不合法。
- 平衡因子 BF
AVL最重要概念。
定义：
BF
=
左子树高度
右子树高度
例如：
4
/ \
2 6
左右高度：
1
1
所以：
BF = 1-1 = 0
再例如：
4
/
2
高度：
左=1
右=0
所以：
BF = 1
AVL允许：
BF=-1
BF=0
BF=1
不允许：
BF=2
BF=-2
4. AVL为什么快
AVL始终保持：
接近平衡
所以高度不会太大。
BST最坏：
高度=n
AVL：
高度≈log₂n
因此：
查找 O(log n)
插入 O(log n)
删除 O(log n)
5. AVL什么时候失衡
插入新节点以后。
例如：
插入：
30
20
10
得到：
30
/
20
/
10
看30：
左高度=2
右高度=0
所以：
BF=2
失衡。
此时需要：
旋转
6. AVL四种失衡
考试必考。
只有四种。
LL
30
/
20
/
10
特点：
左孩子的左边插入
口诀：
LL
右旋
RR
10
20
30
特点：
右孩子的右边插入
口诀：
RR
左旋
LR
30
/
10
20
特点：
左孩子的右边插入
口诀：
LR
先左旋
再右旋
RL
10
30
/
20
特点：
右孩子的左边插入
口诀：
RL
先右旋
再左旋
7. AVL判断口诀
考试最快方法。
发现：
BF=2
说明左边太高
再看：
新增结点
在左孩子左边？
还是左孩子右边？
如果：
左孩子左边
就是：
LL
如果：
左孩子右边
就是：
LR
同理：
BF=-2
说明：
右边太高
看新增结点：
右孩子右边
RR
或者：
右孩子左边
RL
8. AVL结构体
一般和BST一样。
struct TreeNode
{
int val;
struct TreeNode* left;
struct TreeNode* right;
int height;
};
新增：
height
记录高度。
- AVL为什么需要height
因为要算：
BF
而：
BF
=
左高度
右高度
所以每个节点都保存：
height
方便计算。
- 易错点
易错点1
AVL首先是BST
仍然满足：
左小右大
不要忘。
易错点2
AVL不是完全平衡树
允许：
BF=1
BF=0
BF=-1
不是：
必须相等
易错点3
失衡只会有四种：
LL
RR
LR
RL
考试看到图先判断类型。
易错点4
双旋转别背反
口诀：
LR
先左后右
RL
先右后左
AVL总结（考试版）
AVL树
定义：
平衡二叉查找树
首先是BST：
左子树 < 根
右子树 > 根
平衡因子：
BF
=
左高度
右高度
合法：
BF=-1
BF=0
BF=1
失衡：
BF=2
BF=-2
四种失衡：
LL
RR
LR
RL
对应旋转：
LL
右旋
RR
左旋
LR
左旋+右旋
RL
右旋+左旋
复杂度：
查找 O(log n)
插入 O(log n)
删除 O(log n)
