平衡二叉树（注意LR和RL）

一：平衡二叉树的概念

平衡二叉树(Balanced binary tree)又称为AVL树，是一种特殊的二叉排序树，且左右子树的高度之差的绝对值不超过1.

定义：平衡二叉树或为空树,或为如下性质的二叉排序树:

（1）左右子树深度之差的绝对值不超过1;

（2）左右子树仍然为平衡二叉树.

平衡因子BF=左子树深度－右子树深度.

平衡二叉树每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则该二叉排序树就是不平衡的。

二、平衡二叉树调整

　　若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树，然后再调整这个子树，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，无需调整原有其他所有不平衡子树，整个二叉排序树就又成为一棵平衡二叉树。

　　失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。

（1）LL型平衡旋转法

　　由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。

（2）RR型平衡旋转法

　　由于在A的右孩子C 的右子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转代替A作为根结点，A向左下旋转成为C的左子树的根结点。而原来C的左子树则变成A的右子树。

（3）LR型平衡旋转法

　　由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作（先逆时针，后顺时针）。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型，再按LL型处理。

如图中所示，即先将圆圈部分先调整为平衡树，然后将其以根结点接到A的左子树上，此时成为LL型，再按LL型处理成平衡型。

（4）RL型平衡旋转法

　　由于在A的右孩子C的左子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行两次旋转操作（先顺时针，后逆时针），即先将A结点的右孩子C的左子树的根结点D向右上旋转提升到C结点的位置，然后再把该D结点向左上旋转提升到A结点的位置。即先使之成为RR型，再按RR型处理。

如图中所示，即先将圆圈部分先调整为平衡树，然后将其以根结点接到A的左子树上，此时成为RR型，再按RR型处理成平衡型。

记忆：LL是顺时针旋转、RR是逆时针、LR是先逆时针在顺时针，RL是先顺时针在逆时针（记住L是顺时针，R是逆时针，而双旋转从后往前读）

三： 如何判断进行单旋转还是双旋转 （什么时候需要单旋转，而什么时候需要多旋转？）

1.0）高度不平衡需要α点的两棵子树高度差为2，故可得高度不平衡可能出现在下面四种情况中： ① 对α的左儿子的左子树进行一次插入。 ② 对α的左儿子的右子树进行一次插入。 ③ 对α的右儿子的左子树进行一次插入。 ④ 对α的右儿子的右子树进行一次插入。 举例（黄点是α点）： 1.1）单旋转： 插入点不介于 不满足AVL条件的树根 和 树根对应孩子节点之间； （情形①、③ 即 左-左、右-右） 1.2）双旋转：插入点介于 不满足AVL条件的树根 和 树根对应孩子节点之间；（情形②、④ 即 左-右、右-左）