7.3.2.1 AVL 的插入与平衡旋转

教材导航 · 第7章

原书定位

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

先按 BST 插入,再向上找距新结点最近的失衡祖先,调整最小不平衡子树。旋转保持中序次序,并将新的子树根接回原父结点。

插入方向调整
LL:左孩子的左侧对失衡结点右旋
RR:右孩子的右侧对失衡结点左旋
LR:左孩子的右侧先左旋左孩子,再右旋失衡结点
RL:右孩子的左侧先右旋右孩子,再左旋失衡结点

LL、RR 描述插入方向,和最终旋转方向相反。一次插入修复最小失衡子树后,其高度恢复为插入前高度,通常无需继续旋转更高祖先。

最小不平衡子树

最小不平衡子树,原书P288。

LL 右单旋

LL 右单旋,原书P288。

RR 左单旋

RR 左单旋,原书P288。

LR 双旋

LR 双旋,原书P289。

RL 双旋

RL 双旋,原书P289。

AVL 逐步构造过程

AVL 逐步构造过程,原书P290。

对应练习

7.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P287,PDF第299页

原书对照,原书P288,PDF第300页

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