1AVL旋转
21. 前提条件
3
4AVL失衡时：
5
6BF = 2
7
8或者
9
10BF = -2
11
12需要旋转。
13
14目的：
15
16降低树高度
17
18恢复平衡
192. 核心概念
20
21记住：
22
23LL
24
25右旋
26
27----------------
28
29RR
30
31左旋
32
33----------------
34
35LR
36
37先左后右
38
39----------------
40
41RL
42
43先右后左
44
45但是不要死背。
46
47先理解：
48
49什么叫左旋
50
51什么叫右旋
52一、右旋 Right Rotation
531. 前提条件
54
55例如：
56
57 30
58 /
59 20
60 /
61 10
62
63这是：
64
65LL失衡
66
67因为：
68
6930
70
71左边太高
722. 核心思想
73
74把：
75
7620
77
78提上来。
79
80把：
81
8230
83
84压下去。
85
863. 旋转前
87 30
88 /
89 20
90 /
91 10
92
93记：
94
95A = 30
96
97B = 20
98
99T1 = 10
100
101画成：
102
103 A
104 /
105 B
106 /
107 T1
1084. 旋转后
109 20
110 / \
111 10 30
112
113变成：
114
115 B
116 / \
117 T1 A
1185. 右旋口诀
119左孩子上来
120
121根节点下去
1226. 指针变化
123
124旋转前：
125
126 A
127 /
128 B
129 \
130 T2
131
132完整情况：
133
134 A
135 /
136 B
137 / \
138 T1 T2
139
140旋转后：
141
142 B
143 / \
144 T1 A
145 /
146 T2
147
148注意：
149
150T2
151
152变成A的左子树
153
154代码：
155
156struct TreeNode* rightRotate(
157 struct TreeNode* A)
158{
159 struct TreeNode* B = A->left;
160
161 struct TreeNode* T2 = B->right;
162
163 B->right = A;
164
165 A->left = T2;
166
167 return B;
168}
1697. 为什么T2不能丢
170
171很多人第一次学会这样想：
172
17320上去
174
17530下来
176
177完事。
178
179错。
180
181例如：
182
183 30
184 /
185 20
186 / \
187 10 25
188
18925在哪？
190
19125 > 20
192
19325 < 30
194
195所以：
196
19725必须放在
198
19920和30之间
200
201因此：
202
20325
204
205变成30的左子树
206
207即：
208
209T2
210二、左旋 Left Rotation
2111. 前提条件
212
213例如：
214
21510
216 \
217 20
218 \
219 30
220
221这是：
222
223RR失衡
224
225因为：
226
227右边太高
2282. 核心思想
229
230把：
231
23220
233
234提上来。
235
236把：
237
23810
239
240压下去。
241
2423. 旋转前
243 10
244 \
245 20
246 \
247 30
248
249设：
250
251A = 10
252
253B = 20
254
255T3 = 30
256
257画成：
258
259A
260 \
261 B
262 \
263 T3
2644. 旋转后
265 20
266 / \
267 10 30
2685. 左旋口诀
269右孩子上来
270
271根节点下去
2726. 完整情况
273
274旋转前：
275
276 A
277 \
278 B
279 / \
280 T2 T3
281
282旋转后：
283
284 B
285 / \
286 A T3
287 \
288 T2
289
290注意：
291
292T2
293
294变成A的右子树
295
296代码：
297
298struct TreeNode* leftRotate(
299 struct TreeNode* A)
300{
301 struct TreeNode* B = A->right;
302
303 struct TreeNode* T2 = B->left;
304
305 B->left = A;
306
307 A->right = T2;
308
309 return B;
310}
311三、为什么旋转后BST没坏
312
313右旋例子：
314
315 30
316 /
317 20
318 / \
319 10 25
320
321中序：
322
32310 20 25 30
324
325右旋：
326
327 20
328 / \
329 10 30
330 /
331 25
332
333中序：
334
33510 20 25 30
336
337完全一样。
338
339所以：
340
341旋转不会改变BST顺序
342
343只会改变：
344
345树形状
346四、为什么能恢复平衡
347
348例如：
349
35030
351/
35220
353/
35410
355
356高度：
357
358左=2
359
360右=0
361
362BF：
363
3642
365
366失衡。
367
368右旋后：
369
370 20
371 / \
372 10 30
373
374高度：
375
376左=1
377
378右=1
379
380BF：
381
3820
383
384恢复平衡。
385
386五、考试必背图
387LL
388 30
389 /
390 20
391 /
392 10
393
394↓
395
396 20
397 / \
398 10 30
399
400右旋。
401
402RR
40310
404 \
405 20
406 \
407 30
408
409↓
410
411 20
412 / \
413 10 30
414
415左旋。
416
417六、笔记总结
418AVL旋转
419
420目的：
421
422恢复平衡
423
424不改变BST顺序
425
426--------------------------------
427
428右旋：
429
430左孩子上来
431
432根节点下去
433
434T2变成根节点左子树
435
436--------------------------------
437
438左旋：
439
440右孩子上来
441
442根节点下去
443
444T2变成根节点右子树
445
446--------------------------------
447
448LL：
449
450右旋
451
452--------------------------------
453
454RR：
455
456左旋
457
458--------------------------------
459
460口诀：
461
462左边太高
463
464右旋
465
466右边太高
467
468左旋
469
470--------------------------------
471
472旋转不会改变
473
474中序遍历结果
475
476只改变树形状
477
478你后面学 LR 和 RL 的时候，会发现其实根本不是新东西：
479
480LR
481
482先对儿子左旋
483
484再对爷爷右旋
485
486----------------
487
488RL
489
490先对儿子右旋
491
492再对爷爷左旋
493
494本质上还是这两个单旋转的组合。
AVL旋转
- 前提条件
AVL失衡时：
BF = 2
或者
BF = -2
需要旋转。
目的：
降低树高度
恢复平衡
2. 核心概念
记住：
LL
右旋
RR
左旋
LR
先左后右
RL
先右后左
但是不要死背。
先理解：
什么叫左旋
什么叫右旋
一、右旋 Right Rotation
- 前提条件
例如：
30
/
20
/
10
这是：
LL失衡
因为：
30
左边太高
2. 核心思想
把：
20
提上来。
把：
30
压下去。
- 旋转前
30
/
20
/
10
记：
A = 30
B = 20
T1 = 10
画成：
A
/
B
/
T1
4. 旋转后
20
/
10 30
变成：
B
/ \
T1 A
5. 右旋口诀
左孩子上来
根节点下去
6. 指针变化
旋转前：
A
/
B
\
T2
完整情况：
A
/
B
/ \
T1 T2
旋转后：
B
/ \
T1 A
/
T2
注意：
T2
变成A的左子树
代码：
struct TreeNode* rightRotate(
struct TreeNode* A)
{
struct TreeNode* B = A->left;
struct TreeNode* T2 = B->right;
B->right = A;
A->left = T2;
return B;
}
7. 为什么T2不能丢
很多人第一次学会这样想：
20上去
30下来
完事。
错。
例如：
30
/
20
/ \
10 25
25在哪？
25 > 20
25 < 30
所以：
25必须放在
20和30之间
因此：
25
变成30的左子树
即：
T2
二、左旋 Left Rotation
- 前提条件
例如：
10
20
30
这是：
RR失衡
因为：
右边太高
2. 核心思想
把：
20
提上来。
把：
10
压下去。
- 旋转前
10
20
30
设：
A = 10
B = 20
T3 = 30
画成：
A
B
T3
4. 旋转后
20
/
10 30
5. 左旋口诀
右孩子上来
根节点下去
6. 完整情况
旋转前：
A
\
B
/ \
T2 T3
旋转后：
B
/ \
A T3
\
T2
注意：
T2
变成A的右子树
代码：
struct TreeNode* leftRotate(
struct TreeNode* A)
{
struct TreeNode* B = A->right;
struct TreeNode* T2 = B->left;
B->left = A;
A->right = T2;
return B;
}
三、为什么旋转后BST没坏
右旋例子：
30
/
20
/ \
10 25
中序：
10 20 25 30
右旋：
20
/ \
10 30
/
25
中序：
10 20 25 30
完全一样。
所以：
旋转不会改变BST顺序
只会改变：
树形状
四、为什么能恢复平衡
例如：
30
/
20
/
10
高度：
左=2
右=0
BF：
2
失衡。
右旋后：
20
/ \
10 30
高度：
左=1
右=1
BF：
0
恢复平衡。
五、考试必背图
LL
30
/
20
/
10
↓
20
/ \
10 30
右旋。
RR
10
20
30
↓
20
/ \
10 30
左旋。
六、笔记总结
AVL旋转
目的：
恢复平衡
不改变BST顺序
右旋：
左孩子上来
根节点下去
T2变成根节点左子树
左旋：
右孩子上来
根节点下去
T2变成根节点右子树
LL：
右旋
RR：
左旋
口诀：
左边太高
右旋
右边太高
左旋
旋转不会改变
中序遍历结果
只改变树形状
你后面学 LR 和 RL 的时候，会发现其实根本不是新东西：
LR
先对儿子左旋
再对爷爷右旋
RL
先对儿子右旋
再对爷爷左旋
本质上还是这两个单旋转的组合。
