AVL树删除操作旋转再平衡失衡恢复
AVL树删除
看完你能识别删除引发的四种失衡并画出对应旋转
按 空格/→ 演示下一步
1 / 13 页
全部页面点击任意一页，跳回舞台从这页播放
AVL树删除操作旋转再平衡失衡恢复
AVL树删除
看完你能识别删除引发的四种失衡并画出对应旋转
删除 vs 插入：关键区别
上页我们删完节点做了旋转，看起来和插入很像——都是'哪里歪了扭哪里'。但删除有一个插入没有的麻烦：调完一层，上一层可能又歪了。
插入：一次就够
旋转后子树高度复原，上面不会再被连累
删除：高度回缩
旋转后高度仍可能变矮，父节点跟着失衡
沿路径向上回溯
从删除点一路查到根，每站都要看平衡
最坏 log n 次旋转
和树高同阶，不会比这更糟
拆承重墙对应 →AVL树删除
下层拆完，上面每层都要重新测平
删除操作完整流程
自顶向下读：先找到节点并删除，再沿父路径向上回溯，逐层检查是否需要旋转。
图解渲染中…
s4：目标节点的左右子树数量，决定删除方式s8：从被删除节点向上，沿父指针一路返回根s9：删除使子树高度下降，需检查祖先的平衡因子s10：LL/RR 单旋，LR/RL 双旋，恢复局部平衡
右旋：LL型不平衡
LL型失衡用一次右旋修复，分六步把父子关系翻过来。
1
定位失衡节点
找到平衡因子为+2的最深节点A
2
确认LL型
删除发生在A左子树的左叶子
3
锁定旋转轴
A的左孩子L将升为子树的根
4
移交右子树
L的右孩子LR过继给A作左孩子
5
完成反转
A挂到L的右孩子位置
6
更新高度
先L后A，自下而上重算
左旋：RR型不平衡
RR型失衡由右子树的右叶子删除引发，分四步左旋把树重新拉平。
1
识别RR失衡
删完右右后，祖先A平衡因子变成+2，左高右矮
2
右孩子上位
让A的右孩子B替换A的位置，成为子树新根
3
左孩子过继
B原本的左孩子转交给A，作为A新的右孩子
4
A挂到左边
A变成B的左孩子，整棵子树高度复原
先左后右旋：LR型不平衡
删除落在左孩子的右分支，失衡后要左右各旋一次才能摆平。
1
找到失衡点A
A的平衡因子从1跳到2，左边突然变重
2
判定LR型
A的左孩子B偏向右侧（B的平衡因子为-1）
3
对B左旋
B的右孩子C升为父，B退到C的左孩子位置
4
对A右旋
C成为新根，左挂B、右挂A，恢复平衡
先右后左旋：RL型不平衡
删除右子树左叶后，沿路径向上回溯，通过先右后左的双旋恢复平衡。
1
回溯找失衡点
从被删节点向根回溯，定位首个平衡因子变-2的祖先
2
判断为RL型
失衡点右偏，但右孩子的左子树更高，呈RL构型
3
右旋右孩子
对右孩子做右旋，把RL型转化为更易处理的RR型
4
左旋失衡点
对失衡点做左旋，新根就位，从该点到叶子的高度恢复
删除根节点的特殊情况
从删除根节点出发，看替换、回溯、旋转三阶段如何串成完整路径
图解渲染中…
d1：中序后继：右子树中最小的节点g1：回溯方向：从后继原位置向上到根h1：四种失衡对应前4页的旋转方案
删除度为2的节点
度为2节点有两个孩子，直接删会留两个孤儿。前驱还是后继？两种策略等价，但影响哪边子树变矮。
用前驱替代
- 取左子树中最大的节点
- 从左子树最右下角挖出它
- 左子树变矮，可能触发右旋
用后继替代
- 取右子树中最小的节点
- 从右子树最左下角挖出它
- 右子树变矮，可能触发左旋
两者都正确，替换后中序遍历不变。优先选较深那一侧的替代者，能减少后续再平衡的旋转次数。
AVL树删除实现
递归删除配合平衡因子的更新与旋转调整
AVL树删除实现
递归删除配合平衡因子的更新与旋转调整
时间复杂度分析
本图论证删除最坏O(log n)：回溯路径≤树高=O(log n)，每节点工作=O(1)，两步相乘仍是O(log n)。
图解渲染中…
a4：AVL树高严格≤1.44·log₂(n+2)，即O(log n)a7：单旋或双旋修复失衡，仅改常数个指针=O(1)
自测题
点击作答
AVL树删除节点后，判断旋转类型（LL/RR/LR/RL）应依据？
课后思考
先自己琢磨，再对照参考答案看看思路对不对。
1为什么AVL删除可能需要沿途多个祖先节点都旋转，而插入最多只需要一次？
参考答案插入只会让失衡沿新插入路径传一次，旋转一次即可恢复；删除后失衡可能向上蔓延，每层都得重新检查并可能旋转。
2如果把平衡判定从「高度差≤1」放宽到「高度差≤2」，搜索还能保持高效吗？
参考答案高度差放宽后查找退化为接近O(n)，极端情况可能退化成链表；平衡条件是O(log n)查找的保证，不是装饰品。
3删除度为2的节点时，为什么不能直接交换它和前驱/后继的值再删除？
参考答案交换值只改了节点里的数据，没有改树的指针结构，目标位置的子树归属会乱；用前驱/后继替换后才能保证被删节点度≤1。