[数据结构] 平衡二叉查找树 (AVL树)
AVL树(平衡二叉查找树)
AVL树本质上是一颗二叉查找树，但是它又具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为平衡二叉树。下面是平衡二叉树和非平衡二叉树对比的例图：
平衡因子(bf)：结点的左子树的深度减去右子树的深度，那么显然-1<=bf<=1;
AVL树的作用：
我们知道，对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。
例如：我们按顺序将一组数据1,2,3,4,5,6分别插入到一颗空二叉查找树和AVL树中，插入的结果如下图：
由上图可知，同样的结点，由于插入方式不同导致树的高度也有所不同。特别是在带插入结点个数很多且正序的情况下，会导致二叉树的高度是O(N)，而AVL树就不会出现这种情况，树的高度始终是O(lgN).高度越小，对树的一些基本操作的时间复杂度就会越小。这也就是我们引入AVL树的原因。
AVL树的基本操作：
AVL树的操作基本和二叉查找树一样，这里我们关注的是两个变化很大的操作：插入和删除！
我们知道，AVL树不仅是一颗二叉查找树，它还有其他的性质。如果我们按照一般的二叉查找树的插入方式可能会破坏AVL树的平衡性。同理，在删除的时候也有可能会破坏树的平衡性，所以我们要做一些特殊的处理，包括：单旋转和双旋转！
AVL树的插入，单旋转的第一种情况 右旋
由上图可知：在插入之前树是一颗AVL树，而插入之后结点T的左右子树高度差的绝对值不再 < 1,此时AVL树的平衡性被破坏，我们要对其进行旋转。由上图可知我们是在结点T的左结点的左子树上做了插入元素的操作，我们称这种情况为左左情况，我们应该进行右旋转(只需旋转一次，故是单旋转)。具体旋转步骤是：
T向右旋转成为L的右结点，同时，Y放到T的左孩子上。这样即可得到一颗新的AVL树，旋转过程图如下：
左左情况的右旋举例：
AVL树的插入，单旋转的第二种情况 左旋
由上图可知：在插入之前树是一颗AVL树，而插入之后结点T的左右子树高度差的绝对值不再 < 1,此时AVL树的平衡性被破坏，我们要对其进行旋转。由上图可知我们是在结点T的右结点的右子树上做了插入元素的操作，我们称这种情况为右右情况，我们应该进行左旋转(只需旋转一次，故事单旋转)。具体旋转步骤是：
T向右旋转成为R的左结点，同时，Y放到T的左孩子上。这样即可得到一颗新的AVL树，旋转过程图如下：
右右情况的左旋举例：
以上就是插入操作时的单旋转情况！我们要注意的是：谁是T谁是L，谁是R还有谁是X,Y,Z!T始终是开始不平衡的左右子树的根节点。显然L是T的左结点，R是T的右节点。X、Y、Y是子树当然也可以为NULL.NULL归NULL，但不能破坏插入时我上面所说的左左情况或者右右情况。
AVL树的插入，双旋转的第一种情况 左右(先左后右)旋
由上图可知，我们在T结点的左结点的右子树上插入一个元素时，会使得根为T的树的左右子树高度差的绝对值不再 < 1，如果只是进行简单的右旋，得到的树仍然是不平衡的。我们应该按照如下图所示进行二次旋转：
左右情况的左右旋转实例：
AVL树的插入，双旋转的第二种情况 右左(先右后左)旋
由上图可知，我们在T结点的右结点的左子树上插入一个元素时，会使得根为T的树的左右子树高度差的绝对值不再 < 1，如果只是进行简单的左旋，得到的树仍然是不平衡的。我们应该按照如下图所示进行二次旋转：
右左情况的右左旋转实例：
以上关于二叉树的介绍转载自 https://www.cnblogs.com/zhuwbox/p/3636783.html ，很具体，便于理解。
下面提供我所写的插入(建树)操作代码以供参考
#include<stdio.h>
#include<stdlib.h>
//平衡二叉树 AVL树的实现 By Titan
typedef struct AVLNode *Position;
typedef Position AVLTree;
struct AVLNode{
int Data;
Position Left;
Position Right;
int Height;
};
int Max(int a,int b){
return a > b ? a : b;
}
int getHeight(AVLTree T){
if(!T){
return -1;
}else{
return T->Height;
}
}
int getMaxHeight(AVLTree A,AVLTree B){
return Max(getHeight(A),getHeight(B));
}
//定义右单旋
AVLTree S_RR(AVLTree A){
AVLTree B = A->Left;
A->Left = B->Right;
B->Right = A;
A->Height = getMaxHeight(A->Right,A->Left)+1;
B->Height = getMaxHeight(A->Right,A->Left)+1;
return B;
}
//定义左单旋
AVLTree S_LR(AVLTree A){
AVLTree B=A->Right;
A->Right=B->Left;
B->Left=A;
A->Height = getMaxHeight(A->Right,A->Left)+1;
B->Height = getMaxHeight(A->Right,A->Left)+1;
return B;
}
//定义左右双旋(先左旋后右旋)
AVLTree D_LR(AVLTree A){
A->Left=S_LR(A->Left);
AVLTree B=S_RR(A);
return B;
}
//定义右左双旋(先右旋后左旋)
AVLTree D_RL(AVLTree A){
A->Right=S_RR(A->Right);
AVLTree B=S_LR(A);
return B;
}
AVLTree Insert(AVLTree T,int X){
//树空的话直接建树
if(!T){
T=(AVLTree)malloc(sizeof(struct AVLNode));
T->Data=X;
T->Left=T->Right=NULL;
T->Height=0;
}
//插入到左子树
else if(T->Data>X){
T->Left=Insert(T->Left,X);
//判断是否要平衡
if(getHeight(T->Left)-getHeight(T->Right)==2){
// X插入到左树的左边,右单旋转
if(X<T->Left->Data){
T = S_RR(T);
}
// X插入到左树的右边,左右双旋
else if(X>T->Left->Data){
T=D_LR(T);
}
}
}
//插入到右子树
else if(T->Data<X){
T->Right=Insert(T->Right,X);
if(getHeight(T->Right)-getHeight(T->Left)==2){
// X插入到右树的右边,左单旋转
if(X>T->Right->Data){
T = S_LR(T);
}
// X插入到右树的左边,右左双旋
else if(X<T->Right->Data){
T=D_RL(T);
}
}
}// else 没插入就不用旋转了
//更新树的高度
T->Height = getMaxHeight(T->Right,T->Left)+1;
return T;
}
int main(void){
int n,temp;
scanf("%d",&n);
AVLTree T=NULL;
for(int i=0;i<n;i++){
scanf("%d",&temp);
T = Insert(T,temp);
}
printf("%d",T->Data);
}