7.3.2.2 AVL 的删除

教材导航 · 第7章

原书定位

印刷页P289起,对应PDF第301页。下文为目视整理的知识提要;完整内容见原书对照。

先按 BST 规则删除,再沿实际发生高度变化的路径向上检查。对失衡结点选择较高孩子及其较高子树,执行单旋或双旋;高度相同时要结合删除情形选择可保持平衡的调整。

删除修复后子树高度可能继续下降,因此可能需要继续修复更高祖先,直至根;不能把插入时的一次局部修复规则机械套用。总查找与调整时间仍为 O(log⁡n)O(\log n)。

AVL 删除与重新平衡

AVL 删除与重新平衡,原书P290。

对应练习

7.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P289,PDF第301页

原书对照,原书P290,PDF第302页