AVL 树
自平衡二叉搜索树，左右子树高度差不超过 1 — 就像始终保持平衡的天平
概念
现实类比
** 天平**：两边放砝码，一边太重就调整。AVL 树也一样 — 插入后如果不平衡，通过"旋转"恢复平衡。
更多例子：
- 数据库索引：很多数据库用自平衡树实现快速查找
- 文件系统：需要一致性能的目录结构
- 自动补全：需要快速插入和搜索的场景
为什么需要 AVL？
普通 BST 在插入有序数据时会退化成链表。AVL 树通过自动平衡保证所有操作都是 O(log n)。
四种旋转
| 情况 | 平衡因子 | 描述 | 修复 |
|---|---|---|---|
| LL | > 1，插入在左子树的左边 | 左子树太高 | 右旋 |
| RR | < -1，插入在右子树的右边 | 右子树太高 | 左旋 |
| LR | > 1，插入在左子树的右边 | 左右不平衡 | 先左旋再右旋 |
| RL | < -1，插入在右子树的左边 | 右左不平衡 | 先右旋再左旋 |
可视化
复杂度
| 操作 | AVL 树 | BST（最差） |
|---|---|---|
| 搜索 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
决策指南
| 场景 | 推荐 |
|---|---|
| 读多写少 | AVL 树（更平衡，查找更快） |
| 写多读少 | 用红黑树 |
| 需要保证 O(log n) | AVL 树 |
| 小数据集（< 100） | 数组或普通 BST 即可 |