1. 为什么需要AVL树？
想象一下你正在图书馆找一本书。如果书架上的书乱七八糟，你可能需要一本一本地翻找，最坏情况下要翻遍整个图书馆（时间复杂度O(n)）。但如果书籍按照编号有序排列，你就能快速定位（时间复杂度O(logn)）。二叉搜索树就是这个原理，但有个致命缺陷——当插入有序数据时，它会退化成链表，查找效率直接跌到O(n)。
我去年给电商系统做商品分类时就踩过这个坑。当用户按价格从低到高浏览商品时，后台用普通二叉搜索树存储价格数据，结果性能暴跌。后来改用AVL树，查询时间从200ms降到5ms。这就是为什么我们需要自平衡的二叉搜索树——AVL树通过旋转操作自动维持平衡，保证最坏情况下也能保持O(logn)的查询效率。
2. 理解平衡与失衡
AVL树的核心是平衡因子：每个节点的左子树高度减去右子树高度。平衡因子只能是-1、0或1。当插入/删除节点导致某个节点的平衡因子变成±2时，树就失衡了。
举个例子，下图插入节点"9"后：
7 (平衡因子=2) / 6 / 9节点7的左子树高度变成2，右子树高度0，平衡因子=2-0=2，触发失衡。此时需要通过旋转来恢复平衡。
3. 四种旋转策略详解
3.1 LL旋转（右旋）
场景：新节点插入到失衡节点左子树的左子树（LL路径）。比如在下面树中插入"1"：
5 (失衡点) / 3 / 1操作：像拧瓶盖一样向右旋转：
- 抓住失衡节点5的左孩子3
- 把3的右子树4（如果有）挂到5的左边
- 让3成为新的根节点
代码实现：
def right_rotate(node): new_root = node.left node.left = new_root.right new_root.right = node return new_root3.2 RR旋转（左旋）
场景：新节点插入到失衡节点右子树的右子树（RR路径）。比如插入"7"：
3 (失衡点) \ 5 \ 7操作：像拧螺丝一样向左旋转：
- 抓住失衡节点3的右孩子5
- 把5的左子树4（如果有）挂到3的右边
- 让5成为新的根节点
代码实现：
def left_rotate(node): new_root = node.right node.right = new_root.left new_root.left = node return new_root3.3 LR旋转（先左后右）
场景：新节点插入到失衡节点左子树的右子树（LR路径）。比如插入"4"：
5 (失衡点) / 2 \ 4操作：分两步处理：
- 先对左孩子2做左旋，变成LL情况
- 再对根节点5做右旋
实战技巧：我在实现时发现，可以先定位到三个关键节点：失衡节点(5)、它的左孩子(2)、左孩子的右孩子(4)。旋转后4会成为新的局部根。
3.4 RL旋转（先右后左）
场景：新节点插入到失衡节点右子树的左子树（RL路径）。比如插入"6"：
3 (失衡点) \ 8 / 6操作：镜像处理：
- 先对右孩子8做右旋，变成RR情况
- 再对根节点3做左旋
4. 完整AVL树实现要点
插入流程：
- 递归插入新节点
- 回溯时更新每个节点的高度
- 检查平衡因子，若失衡则旋转
删除流程更复杂，需要处理三种情况：
- 删除叶子节点：直接删除，向上检查平衡
- 删除单子节点：用子节点替代，检查平衡
- 删除双子节点：找到前驱/后继替代，递归删除原节点
高度优化：我习惯用缓存策略——每个节点缓存自己的高度，旋转时局部更新，避免全树递归计算。
5. 实战中的性能对比
测试插入10万个随机数：
- 普通BST：最坏情况退化成链表，插入耗时12秒
- AVL树：保持平衡，插入仅需0.3秒
但AVL的旋转有代价：在频繁插入删除的场景下，红黑树可能更合适。不过对于读多写少的场景（如数据库索引），AVL严格的平衡性能优势明显。
6. 常见踩坑与解决
坑1：旋转后忘记更新高度。会导致后续平衡判断错误。我的经验是封装旋转函数，内部自动更新相关节点高度。
坑2：双旋转时顺序错误。LR必须先左旋子节点再右旋父节点，有次我搞反顺序导致树结构破坏。
坑3：删除节点时漏检查多个失衡点。实际项目中遇到过删除一个节点引发上层多个节点连续失衡的情况，需要while循环向上检查直到根节点。
