AVL树：重平衡
看完你能根据失衡形态，推出对应的修复旋转
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
AVL树：重平衡
看完你能根据失衡形态，推出对应的修复旋转
什么是AVL树
上一节我们讲了'重平衡'，那什么是AVL树？它是最早的自平衡二叉搜索树，1962年由两位苏联科学家发明，'AVL'三个字母就取自他们的姓氏。
左右两列最高的人，身高差不能超过1，否则调整站位
AVL树与BBST的关系
认识了 AVL 树，我们再往外看一眼：它不是孤例，而是「平衡二叉搜索树」这个大家族中的明星成员。这页帮你看清它在整个家族里的位置。
汽车、火车、飞机都是交通工具，正如 AVL、红黑树、伸展树都是 BBST
平衡因子的定义
前页说 AVL 追求左右子树「高度差不多」——但「差不多」太模糊。工程师需要一把精确的尺子，把每个节点「偏多少」量化成一个数字。
左端翘起记正、右端翘起记负，差值就是平衡因子
什么是适度平衡
上页平衡因子 BF = hL - hR 只能取 -1、0、1。听起来是三个值，但关键在于：为什么不强制 BF = 0、也就是走完美平衡路线？答案藏在维护代价中。
完美平衡要指针严格归零；适度平衡允许差一格，调整更省
适度平衡 vs 完美平衡
左右两条链分别代表 AVL 适度平衡与完美平衡，最后汇于权衡节点。
平衡因子的计算示例
每节点旁标注 BF = 左高 - 右高。从叶子向上逐层回代，找到 |BF|=2 的失衡节点。
AVL树的基本操作接口
前面我们看到AVL树靠平衡因子判定倾斜程度。落到接口层，哪些操作和普通BST一样，哪些必须额外维护平衡？这是动手前要先分清的问题。
查户口只读不改，搜索同理；迁户口会改记录，写操作需维护平衡
插入/删除操作的流程
AVL的插入和删除都遵循：先做BST基本操作，再向上修复失衡。
失衡的判定
上页走完了插入/删除的主流程，但其中有一环没展开：怎么判定哪些节点失衡需要修？答案很简洁——看平衡因子是否越界。
任何一级与下一级高度差超过 1 就异常，要从最低的异常台阶开始修
LL型失衡与单右旋
左图为LL型失衡（A左-左路径过深），右图为单右旋后的平衡结果。重点看A、B角色互换及T3归属变化。
RR型失衡与单左旋
右子树的右侧过深，执行一次左旋即可恢复
LR型失衡与左右双旋
三阶段展示：失衡态→对Y左旋→对X右旋，每阶段呈现子树结构。
RL型失衡与右左双旋
从左到右读图: 顺着箭头看RL失衡经两次反向旋转, 转化为平衡树的过程。
重平衡的完整流程
重平衡不是一次旋转，而是从发现到回溯的完整闭环。
旋转的本质：中序遍历不变性
四种旋转看完，你有没有想过：旋转之后这棵树还是 BST 吗？答案藏在中序遍历里——旋转只改父子指针，不动节点里的键值。
键对应人、节点对应座位；只调换座位不动人，整体「从矮到高」的相对顺序不变
旋转的代码实现要点
以右旋（LL型）为模板，五行赋值即完成一次旋转。沿箭头读：每个节点是一个中间状态，边上是那一步的指针操作。
自测：失衡类型判断
已知AVL树中某节点A失衡（平衡因子为+2，左偏重），其左孩子为B，新插入节点位于B的右子树中，使B的平衡因子为-1。则A属于哪种失衡类型，应采用哪种旋转？
本章要点回顾
- ✓局部高度差一旦越过2，失衡形态由较高侧子结点的路径决定
- ✓AVL以子树高度差受限换取对树高和操作复杂度的控制
- ✓LL、RR先单旋，LR、RL先反向旋至同向，再单旋
- ✓旋转重接局部结点，修复高度关系并保持中序遍历序列
- ✓插入和删除都要沿访问路径回溯，在最低失衡处完成修复
课后思考
先自己拿笔算一算，再下滑对照参考答案，看思路是否对得上。
参考答案退化为O(n)线性查找。±1的约束保证插入/删除后至多一次旋转即可恢复平衡，树高始终维持在log(n)。放宽后失衡可能沿路径累积，最终退化成链表，整套对数级保证就崩了。
参考答案还守住BST的左小右大关键字序，以及被旋转子树高度的严格下降。前者保证find语义不变；后者才是rotate的真正目的——高度不下降，旋转就成了死循环。
参考答案N(0)=1, N(1)=2, N(h)=1+N(h-1)+N(h-2)。递推与Fibonacci同构（差常数1），由此推出h ≤ c·log_φ(n)，AVL查找的常数因子约为log₂φ ≈ 1.44，介于O(log n)与log₂n之间。