平衡二叉树

AVL树(平衡二叉树)：
　　AVL树本质上是一颗二叉查找树，但是它又具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为平衡二叉树。下面是平衡二叉树和非平衡二叉树对比的例图：

AVL树的作用：
　　我们知道，对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。
　　AVL树的操作基本和二叉查找树一样，这里我们关注的是两个变化很大的操作：插入和删除！
这里我们介绍AVL树的插入操作：
单旋转的情况：
右旋转：
T向右旋转成为L的右结点，同时，Y放到T的左孩子上。

左旋转：
T向右旋转成为R的左结点，同时，Y放到T的左孩子上。这样即可得到一颗新的AVL树，旋转过程图如下：

双旋转：
左右旋转：
在T的左孩子的右子树插入孩子：

这里也就是说明要把不平衡的结点的左孩子先左旋转，然后把自己右旋转就可以了。
我们可以给出一组实例：

右左旋转：
在T的右孩子的左子树插入结点：

同理，先把T结点的右孩子右旋转，再把自己左旋转。
这里我们也给出一个实例：

我们可以对比一下，一般的二叉树的插入操作和我们的这个平衡二叉树插入操作的不同：
比如一组给出一组数字插入进去：
对于一个给定的数组 [3, 2, 1, 4, 5, 6, 7, 10, 9, 8]，如果不适用平衡二叉排序树的生成方法，很有可能得到如下的结果：

这个结果明显是查找效率极低的，所以使用如下的平衡二叉排序树的方法。前三个数字组成的数组如下图所示：

此时，3结点的平衡因子为2，也就是左子树的高度减去右子树的高度为2，显然不满足平衡二叉树的定义，这就要考虑我们的左左情况了，当插入1的时候，3的左孩子的左子树插入1，只要把3右单旋转即可。变成下面这样：

接下来依次插入4，5.
当插入5的时候又是一种情况，也就是右右插入，如下图:

这时只需要把3结点左单旋转即可。变成下面这样：

再插入6时就是2不平衡了，如下：

是上面考虑过的右右情况，只要左单旋转即可。

但是我们仔细一看，这个时候可以看到树已经不是一个二叉树，所以需要对 3 进行处理，由于 3 小于 4 ，所以将 3 连接在 4 的左子树的最右端，得到如下图所示的结果：

然后向其中加入数据节点 7 ，得到如下的结果

其中的 5 6 7 构成了最小不平衡树，将它进行左旋转，得到如下结果

 然后再向其中加入10，9两个点，终于，出现了右左的情况：

结点4，6，7都出现了不平衡，但考虑离插入结点最近的7，7的右孩子的左子树插入了一个结点，那么就要把7的右孩子右单旋转，再把7左单旋转即可，也就是右左双旋转。变成下面这样：

最后向树中添加结点 8，得到的结果如下图所示：

变化如下：

下面给出平衡二叉树的插入以及遍历代码：（删除的情况差不多，我这里是设置的高度，方便比较）

#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct node{
    datatype key;
    struct node* lchild,*rchild;
    int hight;//树高，树根为0
}bsnode;
typedef bsnode* bstree;
int Hight(bstree t){
    if(t==NULL)
         return -1;
    return t->hight;
}
//右单旋转,对应LL型情况
bstree signright(bstree t){
    bstree L=t->lchild;
    t->lchild=L->rchild;
    L->rchild=t;
    t->hight=Hight(t->lchild)>Hight(t->rchild)?Hight(t->lchild):Hight(t->rchild)+1;
    L->hight=Hight(L->lchild)>Hight(L->rchild)?Hight(L->lchild):Hight(L->rchild)+1;
    return L;
}
//左单旋，对应RR型
bstree signleft(bstree t){
    bstree R=t->rchild;
    t->rchild=R->lchild;
    R->lchild=t;
    t->hight=Hight(t->lchild)>Hight(t->rchild)?Hight(t->lchild):Hight(t->rchild)+1;
    R->hight=Hight(R->lchild)>Hight(R->rchild)?Hight(R->lchild):Hight(R->rchild)+1;
    return R;
}
//双旋转，先左后右
bstree doublelr(bstree t){
    t->lchild=signleft(t->lchild);
    return signright(t);//
}
//双旋转，先右后左
bstree doublerl(bstree t){
    t->rchild=signright(t->rchild);
    return signleft(t);
}
bstree inserttree(bstree t,datatype x){
        if(t==NULL){
            t=(bstree)malloc(sizeof(bsnode));
          if(t){
            t->key=x;
            t->lchild=t->rchild=NULL;
            t->hight=0;
           }//树空的时候的操作
       }
        else if(x<t->key){
            t->lchild=inserttree(t->lchild,x);//先插入再旋转
            if(Hight(t->lchild)-Hight(t->rchild)==2){//只有这种情况
                 if(x<t->lchild->key){//左左情况
                     t=signright(t);
                 }
                 else{
                     t=doublelr(t);//左右情况，双旋转，先左后右
                 }
            }
        }
        else if(x>t->key){
            t->rchild=inserttree(t->rchild,x);
            if(Hight(t->rchild)-Hight(t->lchild)==2){
                if(x>t->rchild->key){
                    t=signleft(t);//右右，左单旋转
                }
                else{
                    t=doublerl(t);//右左，双旋转，先右后左
                }
            }
        }
        t->hight=(Hight(t->lchild)>Hight(t->rchild)?Hight(t->lchild):Hight(t->rchild))+1;
        return t;
}
void inorder(bstree p){
    if(p){
        inorder(p->lchild);
        printf("%d ",p->key);
        if(p->lchild)
        printf("lchild: %d ",p->lchild->key);
        else printf("lchild: NULL ");
        if(p->rchild)
        printf("rchild: %d\n",p->rchild->key);
        else printf("rchild: NULL\n");
        inorder(p->rchild);
    }
}   
int main(){
    bstree root=NULL;
    int a[1000],n;
    printf("请输入结点数：\n");
    scanf("%d",&n);
    printf("请输入n个结点:\n");
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);//3 2 1 4 5 6 7 10 9 8
    for(int i=0;i<n;i++)
     root=inserttree(root,a[i]);
     printf("平衡二叉排序树的中序遍历结果为:\n");
     inorder(root);
}