7.3.2.2 AVL 的删除
原书定位
印刷页P289起,对应PDF第301页。下文为目视整理的知识提要;完整内容见原书对照。
先按 BST 规则删除,再沿实际发生高度变化的路径向上检查。对失衡结点选择较高孩子及其较高子树,执行单旋或双旋;高度相同时要结合删除情形选择可保持平衡的调整。
删除修复后子树高度可能继续下降,因此可能需要继续修复更高祖先,直至根;不能把插入时的一次局部修复规则机械套用。总查找与调整时间仍为 。

AVL 删除与重新平衡,原书P290。
对应练习
关联知识
原书对照
展开原书对照截图

