什么是 AVL 树？平衡因子是什么？
简化版
AVL 树是最早的自平衡二叉搜索树，它要求每个节点的左右子树高度差不超过 1。用「平衡因子」衡量：平衡因子 = 左子树高度 − 右子树高度，AVL 要求每个节点的平衡因子只能是 -1、0、+1。一旦插入/删除让某节点的平衡因子变成 ±2，就通过旋转恢复平衡，从而保证树高始终是 O(log n)、操作稳定 O(log n)。
详细版
为什么需要 AVL：普通 BST 按有序数据插入会退化成链，高度变 O(n)、查找退化。AVL 通过强制平衡杜绝这种退化。
平衡因子（Balance Factor, BF）：
BF(node) = height(node.left) − height(node.right)- BF = 0：左右一样高。
- BF = +1：左边高 1（允许）。
- BF = -1：右边高 1（允许）。
- |BF| ≥ 2：失衡，需要旋转调整。
AVL 的不变式：任意节点的 |BF| ≤ 1。它是一种严格平衡——比红黑树更平衡，所以查找更快，但维护平衡的代价也更高。
完整版教学
一、AVL 树解决什么问题
普通二叉搜索树的效率取决于树高，而树高取决于插入顺序。最坏（有序插入）会退化成一条链，高度 n，查找 O(n)。AVL 树（1962 年由 Adelson-Velsky 和 Landis 提出，名字就是三人姓氏首字母）是历史上第一个解决这个问题的方案：在每次插入/删除后主动检查并调整，强制让树保持平衡，把高度锁死在 O(log n)。
二、平衡因子：衡量失衡的量尺
要「维持平衡」，先得能「度量平衡」。AVL 用平衡因子 = 左子树高 − 右子树高。合法的 AVL 树里，每个节点的 BF 只能是 -1、0、+1 三种值。
- 插入或删除会改变某些节点的子树高度，可能让某个祖先的 BF 变成 +2 或 -2。
- 出现 |BF| = 2 就意味着「这个节点太偏了」，必须旋转把它调回来。
实现上，每个节点通常额外存一个高度（或平衡因子）字段，更新时自底向上维护。
三、AVL 保证的高度是多少
AVL 树的严格平衡保证了高度上界。可以证明：含 n 个节点的 AVL 树，高度 h ≤ 1.44·log₂(n)。也就是说 AVL 树的高度最多约为完全平衡树的 1.44 倍，仍然是 O(log n)。所以查找、插入、删除都稳定在 O(log n)——不像普通 BST 有退化到 O(n) 的风险。
推导思路：设高度为 h 的 AVL 树最少有 N(h) 个节点，则
N(h) = N(h-1) + N(h-2) + 1（类似斐波那契），由此解出 h 与 log n 成正比。
四、维持平衡的手段：旋转
AVL 恢复平衡靠旋转（rotation）——一种在保持 BST 有序性的前提下、重新调整局部父子关系以降低树高的操作。根据失衡的方向分四种：LL、RR、LR、RL（详见旋转专题）。旋转是 O(1) 的局部操作，插入后最多一次旋转即可恢复。
五、代价：为严格平衡付出的成本
AVL 的严格平衡带来更快的查找，但也有代价：
- 每个节点要额外存高度/平衡因子。
- 插入删除后要自底向上更新高度、检查平衡、可能旋转，维护成本比红黑树高。
- 尤其删除可能引发从删除点到根一路的多次旋转。
正因如此，很多工程场景（如 Java TreeMap）选择了平衡要求更宽松、调整更少的红黑树，而 AVL 更适合「查多改少」的场景。
六、常见误区与追问
| 考点 | 正确口径 |
|---|---|
| 定义 | 任意节点左右子树高度差不超过 1 |
| 平衡因子 | leftHeight - rightHeight |
| 维护手段 | 插入删除后旋转 |
balanceFactor(node) = height(node.left) - height(node.right)
AVL requires balanceFactor in {-1, 0, 1}AVL 的“严格”体现在每个节点都要满足高度差不超过 1。
- 误区：AVL 只是普通 BST 的别名。 AVL 是自平衡 BST，会在更新后通过旋转维护高度平衡。
- 误区：平衡因子越大越好。 平衡因子只是左右高度差，AVL 要求它只能是 -1、0、1。
- 误区：AVL 查询快是因为节点更多。 查询快来自高度被压到 O(log n)，不是节点内容变化。
- 追问：AVL 和完全二叉树一样吗？ 不一样；AVL 只要求高度差约束，不要求最后一层从左到右填满。
- 追问：AVL 的代价是什么？ 插入删除要维护高度并做旋转，实现和更新成本高于普通 BST。
- 追问：适合什么场景？ 读多写少、对查询延迟敏感的有序集合适合 AVL。
七、加强记忆
AVL 树是最早的自平衡 BST，不变式是每个节点左右子树高度差 ≤ 1，用平衡因子（左高 − 右高，取值只能 -1/0/+1） 度量。插入/删除让某节点 |BF|=2 就旋转恢复。它保证高度 ≤ 1.44·log₂n、操作稳定 O(log n)，杜绝了普通 BST 的退化。代价是要存高度、维护成本高（尤其删除），故「查多改少」用 AVL、通用场景常用红黑树。