AVL旋转
1. 前提条件

AVL失衡时：

BF = 2

或者

BF = -2

需要旋转。

目的：

降低树高度

恢复平衡
2. 核心概念

记住：

LL

右旋

----------------

RR

左旋

----------------

LR

先左后右

----------------

RL

先右后左

但是不要死背。

先理解：

什么叫左旋

什么叫右旋
一、右旋 Right Rotation
1. 前提条件

例如：

      30
     /
   20
   /
 10

这是：

LL失衡

因为：

30

左边太高
2. 核心思想

把：

20

提上来。

把：

30

压下去。

3. 旋转前
        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
1. 前提条件

例如：

10
  \
   20
     \
      30

这是：

RR失衡

因为：

右边太高
2. 核心思想

把：

20

提上来。

把：

10

压下去。

3. 旋转前
    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

先对儿子右旋

再对爷爷左旋

本质上还是这两个单旋转的组合。