AVL 树
AVL 树在二叉搜索树节点中保存高度。当局部平衡因子达到 +2 或 -2 时，通过旋转恢复平衡，保证搜索与插入为 O(log n)。依次插入 10..70 的七个整十数，AVL 的边高度为 2，普通 BST 为 6，最长搜索路径从七个节点降为三个。
旋转只改动附近两三个节点的父子关系，不重建整棵树。中间键移到局部根，键的中序排列保持不变。
AVL 树如何工作
每个节点仍满足 BST 的左小右大规则，另存：
height(node) = 1 + max(height(node.left), height(node.right))
本课按边计高度，null 为 -1，叶子为 0。平衡因子为：
BF(node) = height(node.left) - height(node.right)
BF 为 -1、0、+1 时合法。插入叶子后，递归沿祖先回溯：先更新高度，再计算 BF。+2 表示左侧过高，-2 表示右侧过高。
插入修复回溯中遇到的第一个失衡祖先。一次修复可能需要单旋或双旋。修复后，该子树恢复到插入前的高度，更高祖先无需再旋转。因此是“最多一个修复位置”，不是“最多一次旋转”。
四种旋转情况
第一个字母表示较重的一侧，第二个表示新键相对重侧孩子的方向。
| 情况 | 路径 | 修复 |
|---|---|---|
| LL | 左，再左 | 右旋 |
| RR | 右，再右 | 左旋 |
| LR | 左，再右 | 先对孩子左旋，再对祖先右旋 |
| RL | 右，再左 | 先对孩子右旋，再对祖先左旋 |
LR、RL 的内折路径要先变成外侧直线，再让中间键升到局部根。
旋转还会转移中间子树 T2。例如左旋提升右孩子时，该孩子原来的左子树要成为降级节点的右子树，因为它的键位于两旋转键之间。先改连接，再更新降级节点高度，最后更新提升节点高度。
本课只实现插入与搜索。删除可能缩短子树，多个祖先都可能需要修复，不能直接套用插入的一处修复结论。
逐步演示
默认顺序为 insert 30, insert 20, insert 10, insert 25, insert 28, insert 29, search 29。
- 插入 30：空根接入高度 0 的叶子。对照 BST 同样以 30 为根。
- 插入 20：放到 30 左侧。30 高度为 1，
BF(30) = 0 - (-1) = +1，无需修复。 - 插入 10：沿 30、20 到左空位。回溯时 20 高度 1、BF +1；30 高度 2、BF +2。路径 LL，右旋提升 20，左右孩子为 10、30。
- 插入 25：从 20 向右到 30，再向左。30 左高一层，20 右高一层，都合法。
- 插入 28：路径
20 -> 30 -> 25 -> right。30 的 BF 到 +2，但左孩子 25 向右重，属于 LR。先左旋把 28 提到 25 上方，再右旋把 28 提到 30 上方。局部根 28，左右为 25、30。 - 插入 29：路径
20 -> 28 -> 30 -> left。根 20 的 BF 到 -2，新键位于其右孩子 28 的右侧，属于 RR。左旋提升 28。原来根为 25 的T2从28.left移到20.right，仍位于 20 与 28 之间。最终 AVL 边高度 2，同顺序的普通 BST 高度 4。 - 搜索 29：AVL 访问
28 -> 30 -> 29，三次探测；普通 BST 访问30 -> 20 -> 25 -> 28 -> 29，五次探测。键集合相同，路径长度由形状决定。
回溯逐个祖先进行：更新高度、计算 BF、判断形状、修复最低失衡点。小树可在路径旁显示高度，大树把算式放到工作台，避免标签遮挡结构。
时间与空间复杂度
| 操作 | 时间 | 本实现额外空间 |
|---|---|---|
| 搜索 | O(log n) | 迭代，O(1) |
| 插入 | O(log n) | 递归栈，O(log n) |
| 单旋 | O(1) | O(1) |
| 双旋 | O(1) | O(1) |
高度界来自节点数递推。令 N(h) 为边高度 h 的 AVL 最少节点数，最稀疏的合法孩子高度分别为 h - 1、h - 2：
N(-1) = 0, N(0) = 1, N(h) = 1 + N(h - 1) + N(h - 2)
所以 N(h) = F(h + 3) - 1。斐波那契数指数增长，高度因此为对数级，可用约 h <= 1.44 log2(n + 2) 表达上界。搜索走一条路径；插入先下行再回溯，外加一次常数规模修复，不会再乘一个旋转层数。
何时使用 AVL
查找频繁、需要较紧高度界时，AVL 值得考虑，但写入后要维护高度。红黑树允许更宽松的形状，更新较多的有序结构常采用它。普通 BST 更简单，却让高度取决于插入顺序；有序或恶意输入可能把它变成线性查找。
边界情况
- 空树：搜索零次节点探测，首次插入创建高度 0 的根。
- 重复键：在已有节点停止；节点数、两棵树的形状和存储高度都不变。
- 内侧失衡：LR、RL 要双旋，只做外侧旋转可能仍失衡。
- 空
T2：旋转仍有效，只是没有非空子树要转移。 - 显示上限：最多 15 个节点，属于画布限制，不是 AVL 固定容量。
常见错误
- 平衡因子符号用反。 本课是左高减右高；采用相反定义时，所有判定也必须反转。
- 混用高度约定。 null 为 -1、叶子为 0，不能把叶子改成 1 却保留其他计算。
- 改线前计算新高度。 旧孩子只能得到旧高度。改线后先更新降级节点，再更新提升节点。
- 丢失
T2。 必须放回两个键之间；丢失会删数据，放错侧会破坏 BST 顺序。 - 左重就判 LL。 重侧孩子可能向内，需检查第二个方向。
- 插入后在所有祖先旋转。 最低失衡点修复后，继续旋转合法祖先没有必要。