AVL树

1. 定义

AVL 树（Adelson-Velsky and Landis Tree）是最早被提出的 平衡二叉搜索树。
它的判定条件是：

二叉搜索树（BST）性质

任意节点的左子树上所有节点的值 < 当前节点的值；
任意节点的右子树上所有节点的值 > 当前节点的值。

平衡性

对任意节点，|左子树高度 - 右子树高度| ≤ 1；
并且它的左右子树也都是 AVL 树。

2. 特点

二叉搜索树性质：保持节点值的有序性，支持高效查找。
平衡性：避免树退化为链表，保证操作效率。
时间复杂度：查找、插入、删除的平均与最坏情况复杂度均为 $O(\log n)$。
平衡因子 (Balance Factor, BF)：
- 定义：BF = 左子树高度 − 右子树高度；
- 取值范围：{-1, 0, +1}。

3. AVL 树的四种旋转（LL、RR、LR、RL）

当 插入或删除节点 导致某个节点的 平衡因子（BF）超出 {-1,0,1}，树就失衡了。为了恢复平衡，需要进行 旋转操作，调整树结构。AVL 树有 四种典型失衡类型，对应不同的旋转方法：

3.1 LL 型（Left-Left）

在某个节点的 左子树的左子树 插入节点导致失衡

解决方法：右旋

原始树：
      A
     /
    B

插入 C 后形成 LL 型失衡：
      A             ← 节点 A BF = +2 (失衡)
     /
    B
   /
  C               ← 新插入的 C

右旋操作（针对 A）后恢复平衡：
      B             ← B 成为新的根
     / \
    C   A           ← A 下移为右子树，C 保持左子树

单旋右旋（Right Rotation）：失衡节点下移，成为左孩子的 右子节点。

3.2. RR 型（Right-Right）

在某个节点的 右子树的右子树 插入节点导致失衡

解决方法：左旋

原始树：
      A
       \
        B

插入 C 后形成 RR 型失衡：
      A             ← 节点 A BF = -2 (失衡)
       \
        B
         \
          C         ← 新插入的 C

左旋操作（针对 A）后恢复平衡：
      B             ← B 成为新的根
     / \
    A   C           ← A 下移为左子树，C 保持右子树

单旋左旋（Left Rotation）：失衡节点下移，成为右孩子的 左子节点。

3.3. LR 型（Left-Right）

在某个节点的 左子树的右子树 插入节点导致失衡

解决方法：先左旋再右旋

原始树：
      A
     /
    B

插入 C 后形成 LR 型失衡：
      A             ← 节点 A BF = +2 (失衡)
     /
    B
     \
      C           ← 新插入的 C

先左旋（针对 B）：
      A
     /
    C
   /
  B               ← B 下移为左子树，C 升为 B 的父节点

再右旋（针对 A）后恢复平衡：
      C             ← C 成为新的根
     / \
    B   A           ← B 成为左子树，A 成为右子树

“LR 型（Left-Right）：在某节点 A 的左子树 B 的右子树插入节点 C 导致失衡 → 先对 B 做左旋，让 C 升到 B 的位置，B 成为 C 的左孩子 → 然后对 A 做右旋，让 C 升到 A 的位置，A 成为 C 的右孩子，B 保持左孩子。

3.4. RL 型（Right-Left）

在某个节点的 右子树的左子树 插入节点导致失衡

解决方法：先右旋再左旋

原始树：
      A
       \
        B

插入 C 后形成 RL 型失衡：
      A             ← 节点 A BF = -2 (失衡)
       \
        B
       /
      C           ← 新插入的 C

先右旋（针对 B）：
      A
       \
        C
         \
          B       ← B 下移为右子树，C 升为 B 的父节点

再左旋（针对 A）后恢复平衡：
      C             ← C 成为新的根
     / \
    A   B           ← A 成为左子树，B 成为右子树

RL 型（Right-Left）：在某节点 A 的右子树 B 的左子树插入节点 C 导致失衡 → 先对 B 做右旋，让 C 升到 B 的位置，B 成为 C 的右孩子 → 然后对 A 做左旋，让 C 升到 A 的位置，A 成为 C 的左孩子，B 保持右孩子。

4. 应用场景

适用于 查找远多于更新 的场景（因为插入/删除可能触发旋转，维护成本较高）；
常用于：数据库索引、编译器符号表、内存搜索结构。
若更新操作非常频繁，通常会用 红黑树 替代，因为它旋转次数更少，维护平衡更“宽松”。