AVL 树的四种旋转（LL、RR、LR、RL）是怎么回事？

简化版

当某节点失衡（平衡因子变成 ±2）时，按「失衡节点 → 更高子树 → 更高孙子」的方向分四种：LL（左-左，右旋一次）、RR（右-右，左旋一次）、LR（左-右，先对左孩子左旋、再对自己右旋）、RL（右-左，先对右孩子右旋、再对自己左旋）。LL/RR 是「同向」用单旋，LR/RL 是「拐弯」用双旋。旋转在保持 BST 有序性的前提下降低树高。

详细版

失衡类型由「从失衡节点往下、连续两步走向更高子树」的方向命名：

类型	失衡形态	调整
LL	失衡节点的左子树的左边过高	对失衡节点右旋一次
RR	失衡节点的右子树的右边过高	对失衡节点左旋一次
LR	失衡节点的左子树的右边过高	先对左孩子左旋，再对失衡节点右旋
RL	失衡节点的右子树的左边过高	先对右孩子右旋，再对失衡节点左旋

右旋（以失衡节点 y 为例，其左孩子为 x）：

      y                x
     / \             /   \
    x   T3   右旋    x.l   y
   / \       ——→          / \
  x.l x.r              x.r  T3

x 上位成为新根，y 变成 x 的右孩子，x 原来的右子树 x.r 挂到 y 的左边。左旋是它的镜像。

完整版教学

一、旋转的本质：保持有序性地「换根降高」

旋转是把一棵子树里的父子关系重新连接，让原本过高的一侧降下来。关键是旋转不破坏 BST 的中序有序性——旋转前后中序遍历结果完全相同，只是树的形状变矮了。这是旋转能用来平衡 BST 的根本原因。

以右旋为例：x < x.r < y（因为 x 是 y 的左孩子、x.r 是 x 的右子树），旋转后 x 当根、y 当右孩子、x.r 挂到 y 左边，中序仍是 x.l, x, x.r, y, T3，顺序不变。

二、LL 型：单次右旋

「LL」指失衡节点的左孩子的左子树太高。这种「一条直线向左倾斜」的失衡，只需对失衡节点做一次右旋，把左孩子提上来当根，失衡节点降为右孩子，树就平衡了。

插入导致：        右旋后：
    3(BF=2)          2
   /                / \
  2               1   3
 /
1

三、RR 型：单次左旋

「RR」是 LL 的镜像——失衡节点的右孩子的右子树太高，「向右倾斜的直线」。对失衡节点做一次左旋即可，把右孩子提上来当根。

插入导致：        左旋后：
  1(BF=-2)          2
   \               / \
    2             1   3
     \
      3

四、LR 型和 RL 型：为什么要双旋

「LR」指失衡节点的左孩子的右子树太高——这是「先向左、再向右」的拐弯形状。这种情况单次右旋解决不了（旋完还是失衡，只是换了个方向拐弯）。必须两步：

先对左孩子做一次左旋，把「拐弯」的 LR 形状«掰直»成 LL 形状。
再对失衡节点做右旋，按 LL 处理。

LR 失衡:      先对左孩子左旋:    再对根右旋:
    3            3                  2
   /            /                  / \
  1            2                  1   3
   \          /
    2        1

RL 型是它的镜像：先对右孩子右旋、再对失衡节点左旋。记忆口诀：「同向单旋、拐弯双旋」，双旋的第一步总是「把孙子那条拐弯掰成一条直线」。

五、如何判断用哪种旋转

看失衡节点的平衡因子和它较高孩子的平衡因子的符号：

失衡节点 BF = +2（左偏）、左孩子 BF ≥ 0 → LL（右旋）。
失衡节点 BF = +2、左孩子 BF < 0 → LR（左孩子左旋 + 右旋）。
失衡节点 BF = -2（右偏）、右孩子 BF ≤ 0 → RR（左旋）。
失衡节点 BF = -2、右孩子 BF > 0 → RL（右孩子右旋 + 左旋）。

同号（都偏一侧）用单旋，异号（拐弯）用双旋。每次旋转都是 O(1) 局部操作，旋完更新相关节点高度即可。

六、常见误区与追问

考点	正确口径
LL	左左外侧重，用右旋
RR	右右外侧重，用左旋
LR	左右内侧重，先左旋左子，再右旋
RL	右左内侧重，先右旋右子，再左旋

LL: rotateRight(z)
RR: rotateLeft(z)
LR: z.left = rotateLeft(z.left); rotateRight(z)
RL: z.right = rotateRight(z.right); rotateLeft(z)

旋转不是打乱顺序，而是在保持中序序列不变的前提下降低高度。

误区：旋转会破坏 BST 有序性。 正确旋转只改变局部父子关系，中序序列保持不变，因此 BST 性质仍成立。
误区：LL 和 LR 都用一次右旋。 LR 是折线结构，先把它转成 LL，再右旋。
误区：判断旋转只看失衡节点。 还要看较高子树的方向，外侧是单旋，内侧是双旋。
追问：旋转后谁成为新根？ 单旋时较高子节点上升为局部根，原失衡节点下降为它的孩子。
追问：为什么双旋能修复内侧失衡？ 第一次旋转把折线拉直，第二次旋转再降低整体高度。
追问：旋转后要更新哪些高度？ 至少更新原失衡节点和新局部根，双旋还要更新中间节点相关高度。

七、加强记忆

AVL 四种旋转按失衡方向命名：LL 右旋、RR 左旋（同向直线，单旋）；LR 先左旋左孩子再右旋、RL 先右旋右孩子再左旋（拐弯，双旋，第一步先「掰直」成单旋形态）。口诀「同向单旋、拐弯双旋」。旋转保持中序有序性不变、只降低树高，是 O(1) 局部操作。判断类型看失衡节点与其高孩子 BF 的符号是否同号。

简化版

详细版