AVL树
定义
AVL树是最早的自平衡二叉搜索树（BST），由Adelson-Velsky和Landis在1962年提出。它通过严格要求左右子树高度差 ≤ 1来保证树的平衡，从而保证所有操作（查找/插入/删除）的时间复杂度为 O(log N)。
核心特性
- 平衡因子：每个节点的平衡因子 = 左子树高度 - 右子树高度，取值范围为 {-1, 0, 1}
- 严格平衡：任何节点的左右子树高度差不超过1
- 旋转操作：插入/删除后可能破坏平衡，需要通过旋转（左旋/右旋/左右旋/右左旋）恢复平衡
与红黑树对比
| 维度 | AVL树 | 红黑树 |
|---|---|---|
| 平衡严格度 | 严格（左右子树高度差 ≤1） | 较宽松（允许黑高差） |
| 插入/删除旋转次数 | 较多（可能需要多次旋转） | 较少 |
| 查找速度 | 更快（树高更平衡，≤ 1.44log(N+2)） | 稍慢（树高≤ 2log(N+1)） |
| 适用场景 | 查找频繁的场景 | 插入删除频繁的场景（如Java TreeMap） |
| 存储空间 | 需要存储平衡因子或树高 | 只需要1位存储颜色（红/黑） |
旋转操作
- 左旋（Left Rotation）：右子树过高时，将当前节点左旋
- 右旋（Right Rotation）：左子树过高时，将当前节点右旋
- 左右旋（Left-Right Rotation）：先对左子树左旋，再对当前节点右旋
- 右左旋（Right-Left Rotation）：先对右子树右旋，再对当前节点左旋