7.3.2.1 AVL 的插入与平衡旋转
原书定位
印刷页P287起,对应PDF第299页。下文为目视整理的知识提要;完整内容见原书对照。
先按 BST 插入,再向上找距新结点最近的失衡祖先,调整最小不平衡子树。旋转保持中序次序,并将新的子树根接回原父结点。
| 插入方向 | 调整 |
|---|---|
| LL:左孩子的左侧 | 对失衡结点右旋 |
| RR:右孩子的右侧 | 对失衡结点左旋 |
| LR:左孩子的右侧 | 先左旋左孩子,再右旋失衡结点 |
| RL:右孩子的左侧 | 先右旋右孩子,再左旋失衡结点 |
LL、RR 描述插入方向,和最终旋转方向相反。一次插入修复最小失衡子树后,其高度恢复为插入前高度,通常无需继续旋转更高祖先。

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

LL 右单旋,原书P288。

RR 左单旋,原书P288。

LR 双旋,原书P289。

RL 双旋,原书P289。

AVL 逐步构造过程,原书P290。
对应练习
关联知识
原书对照
展开原书对照截图


