平衡二叉树

平衡二叉树（AVL 树）：严格平衡的二叉查找树

平衡二叉树（AVL 树）是一种自平衡的二叉查找树，其核心特性是左右子树的高度差（平衡因子）的绝对值不超过 1。通过严格的平衡约束和旋转操作，AVL 树保证了树的高度始终为O(logn)，从而确保查找、插入、删除等操作的时间复杂度稳定在O(logn)，避免了普通二叉查找树在极端情况下的性能退化。

AVL 树的核心定义与特性

平衡因子（Balance Factor）

定义：对于 AVL 树中的每个节点，平衡因子 = 左子树高度 - 右子树高度。
约束：所有节点的平衡因子必须满足 -1 ≤ 平衡因子 ≤ 1。

核心特性

满足二叉查找树的所有性质（左子树节点值 < 根节点值 < 右子树节点值）。
左右子树均为 AVL 树（递归定义）。
树的高度严格控制在O(logn)（对于 n 个节点的 AVL 树，高度约为1.44log(n+2)-1.328）。

AVL 树的平衡维护：旋转操作

当插入或删除节点导致平衡因子的绝对值超过 1 时，AVL 树通过旋转操作恢复平衡。旋转的目标是调整节点位置，使平衡因子重新满足[-1, 1]的约束，同时保持二叉查找树的有序性。

1. 左旋（Left Rotation）

适用于右子树过高的场景（平衡因子为 - 2），通过将节点与其右子节点旋转，降低右子树高度。

操作步骤：

设节点A为失衡节点（平衡因子 =-2），其右子节点为B。
将B的左子树作为A的右子树。
将A作为B的左子树。
更新A和B的高度。

左旋前：       左旋后：
  A           B
   \         / \
    B   →   A   C
   / \       \
  D   C       D

2. 右旋（Right Rotation）

适用于左子树过高的场景（平衡因子 = 2），通过将节点与其左子节点旋转，降低左子树高度。

操作步骤：

设节点A为失衡节点（平衡因子 = 2），其左子节点为B。
将B的右子树作为A的左子树。
将A作为B的右子树。
更新A和B的高度。

右旋前：       右旋后：
    A         B
   /         / \
  B   →     C   A
 / \           /
C   D         D

3. 复合旋转（左右旋与右左旋）

当失衡节点的子树与孙树方向相反时，需先对子树旋转，再对失衡节点旋转。

（1）左右旋（Left-Right Rotation）

场景：失衡节点A的左子树B的右子树过高（A平衡因子 = 2，B平衡因子 =-1）。
操作：先对B左旋，再对A右旋。

左右旋前：     左旋B后：      右旋A后：
    A           A             C
   /           /             / \
  B     →     C     →       B   A
   \         /
    C       B

（2）右左旋（Right-Left Rotation）

场景：失衡节点A的右子树B的左子树过高（A平衡因子 =-2，B平衡因子 = 1）。
操作：先对B右旋，再对A左旋。

右左旋前：     右旋B后：      左旋A后：
A             A             C
 \             \           / \
  B     →       C     →   A   B
 /               \
C                 B

AVL 树的插入操作

插入节点后，需从插入位置向上回溯，更新各节点的高度并检查平衡因子。若发现失衡（平衡因子绝对值 > 1），则根据失衡类型执行相应旋转。

步骤总结：

按二叉查找树规则插入新节点（默认高度为 1）。
从新节点的父节点开始，向上更新各节点的高度。
对每个节点计算平衡因子，若失衡：
- 左子树过高（平衡因子 = 2）：
  - 左子节点平衡因子≥0 → 右旋。
  - 左子节点平衡因子 =-1 → 左右旋。
- 右子树过高（平衡因子 =-2）：
  - 右子节点平衡因子≤0 → 左旋。
  - 右子节点平衡因子 = 1 → 右左旋。

AVL 树的删除操作

删除操作比插入更复杂，需先按二叉查找树规则删除节点，再向上回溯调整平衡：

若删除的是叶子节点或单子节点，直接移除并更新父节点指针。
若删除的是双子节点，用其中序后继（或前驱）替代，再删除后继节点。
从删除节点的父节点开始，向上更新高度并检查平衡因子，必要时执行旋转。

AVL 树与红黑树的对比

特性	AVL 树	红黑树
平衡严格性	严格平衡（平衡因子≤1）	近似平衡（最长路径≤2× 最短路径）
旋转次数	插入最多 2 次，删除可能多次	插入最多 2 次，删除最多 3 次
空间开销	需存储高度信息	需存储颜色信息（开销更小）
查找效率	略高（树高更矮）	稍低（树高略高）
插入 / 删除效率	较低（旋转频繁）	较高（旋转较少）

适用场景

查询密集型场景：如数据库索引、字典查询等，AVL 树的严格平衡能保证更高的查询效率。
不适合插入 / 删除频繁的场景（旋转操作多，性能开销大）。

总结

AVL 树通过严格的平衡因子约束和旋转操作，确保了二叉查找树的高度始终为O(logn)，从而提供稳定的O(logn)时间复杂度操作。其核心是通过左旋、右旋、左右旋、右左旋四种旋转，在插入和删除后快速恢复平衡。与红黑树相比，AVL 树更适合查询频繁的场景，而红黑树在插入 / 删除频繁的场景中表现更优