[数据结构]平衡二叉树的旋转

平衡二叉树（Balanced binary tree）是由Adelson-velskii 和Landis于1962年提出的，所以又称为AVL树。

先来看定义：

1. 它是一颗空树，或者：2、3
2. 它的左右两个子树的高度差的绝对值不超过1
3. 左右两个子树都是一棵平衡二叉树

 相关该概念：

平衡因子 = 左子树高 - 右子树高（只能是-1，0，1，绝对值超过1，则不满足平衡二叉树的性质）

 其实根据AVL的定义来看，貌似AVL树和二叉排序树并没有太大的关系，二叉排序树并不要求平衡，而平衡树也没有要求有序。

 

但是考虑一颗二叉排序树，我们总是期望树的高度是最低的，即logN，这样当我们进行搜索的时候才能保证高效，但是当我们对一个递增序列进行排序时，会发现BST已经退化成了一个链表，查找事件也退化到了O(n)。因此我们总希望排序二叉树是保持平衡的，从而能达到查找效率的高效化，AVL树就是诞生在这种需求之下的。

因此很多教材上将AVL树定义在BST树的基础之上，也是不无道理的。有人AVL树将其称为平衡二叉排序树。

 

下图所示为AVL树和非平衡树：

 

AVL树相关算法：

 

平衡二叉树的建立：

AVL树的建立过程和二叉排序树是一样的，也是将关键字逐个插入到空树中的过程，不同的是，建立AVL树的过程，对于每一个插入操作都要进行检查，看是否新关键字的插入而导致原AVL树失去平衡，如果失衡，就要进行平衡调整。

 

平衡调整：

假设向AVL中插入一个新节点破坏了平衡，首先要找出插入新节点后失去平衡的最小子树，然后再调整这个子树。值得注意的是：当失去平衡的最小子树被调整为AVL树之后，其他所有的不平衡子树无需调整，整个AVL树就会成为一颗AVL树。

 

这里有个概念：失去平衡的最小子树。所谓的失去平衡的最小子树是以距离插入节点最近，且平衡因子绝对值大于1的节点为根的子树。

 

但是为什么只需要调整失衡的最小子树，其他的都不需要调整就全部平衡了呢？

比如说节点A，有两个子节点B、C，其中插入新节点之后，C节点失去平衡，这时受影响的只可能是C的祖先节点。假设插入新节点之前A的平衡因子是0，则C失衡后，A并不失衡，所以只调整C即可。同理，当A的平衡因子是1，也不影响A的平衡性。当A的平衡因子是-1时，C失衡后，A的平衡因子变成了-2，但是经过调整，C的高度势必会减1，则A的平衡因子又变成了-1，证毕。

 

 

AVL树的调整主要有以下四种：(AVL树的调整部分摘自网络资源)

PS：这里的L、R是指插入节点位于失衡父节点的位置。比如LL表示插入节点在失衡节点的左子树的左子树上。同理，RL指插入节点在失衡节点的右子树的左子树上。以此类推。

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型处理成平衡型。

 

平衡化靠的是旋转。参与旋转的是3个节点（其中一个可能是外部节点NULL），旋转就是把这3个节点转个位置。注意的是，左旋的时候p->right一定不为空，右旋的时候p->left一定不为空，这是显而易见的。

 

 

如果从空树开始建立，并时刻保持平衡，那么不平衡只会发生在插入删除操作上，而不平衡的标志就是出现bf == 2或者 bf == -2的节点。

 

 

 

删除操作：

AVL树的删除操作主要有以下三种：

以下图为例：

1. 叶节点——直接删除，比如说BEF，可直接删除，并不会影响平衡性。原因很简单，自己想╮(╯_╰)╭

2. 包含一颗子树的节点——比如节点C，直接将其子树的根节点（E）取代它的位置。

3. 包含两颗子树的节点——比如A，D。这种情况看似复杂，其实可以转换成第1或者第2种情况。以D为例，首先找到D的前驱结点F或者后继结点C，将D用F或者C替换掉，再删除F（第一种情况）或者C（第二种情况）。