AVL 树的平衡因子怎么定义，失衡后有哪四种调整方式?

核心考点

AVL 树的平衡因子定义、失衡类型判断及四种旋转调整，重点掌握 LL、RR、LR、RL 型的旋转方向。

参考答案(答题要点)

1.平衡因子定义：通常定义为“左子树高度减右子树高度”，即 BF=左子树高度-右子树高度。AVL 树要求每个结点的平衡因子只能取 -1、0、1。若绝对值大于 1，则说明该结点失衡。

2.LL 型：在失衡结点的左孩子的左子树插入导致失衡，采用右旋调整。

3.RR 型：在失衡结点的右孩子的右子树插入导致失衡，采用左旋调整。

4.LR 型：在失衡结点的左孩子的右子树插入导致失衡，先对左孩子左旋，再对失衡结点右旋。

5.RL 型：在失衡结点的右孩子的左子树插入导致失衡，先对右孩子右旋，再对失衡结点左旋。

6.总结：判断类型看“失衡结点到新插入结点”的路径前两步方向。LL 右旋，RR 左旋，LR 先左后右，RL 先右后左。调整对象是最小失衡子树。

易错提醒

平衡因子的左右顺序要全书统一，不能一会儿左减右、一会儿右减左。旋转调整针对的是最小失衡子树，不是整棵树。LR 和 RL 型不能只旋一次，必须按“先孩子、后结点”的顺序旋转。旋转后该子树高度通常恢复为插入前高度。

今日小测

某结点平衡因子为 2，其左孩子平衡因子为 -1，属于哪种失衡类型?应如何调整?

答案：属于 LR 型。先对左孩子左旋，再对该结点右旋。