7.3.2 AVL 平衡二叉树

AVL要求每结点左右子树高度差绝对值不超过1。插入后从下向上找首个失衡点：LL右旋、RR左旋、LR先左后右、RL先右后左。删除可能使多个祖先连续失衡，需一路向上修复。

手工推演

插入30,10,20形成LR：先对10左旋，20上升；再对30右旋，得到20根、10左、30右。三者中序不变10,20,30。

结构与代码

结点保存height，更新为1+max左右高。旋转先保存中间子树，再改链接，最后先更新下降结点再更新新根。

正确性

旋转保持中序次序，同时把高侧高度降低；四型覆盖插入路径相对失衡点的全部方向组合。

错解反馈

按关键字大小猜旋转而不看路径；高度更新顺序错；删除只修复一次。

迁移训练

插入10,30,20是什么类型？答案RL：先右旋30，再左旋10，20为根。