平衡二叉树

#include<bits/stdc++.h>
#define maxsize 100
using namespace std;

typedef struct avlnode *position;
typedef position avltree;
struct avlnode{
    int data;
    avltree left;
    avltree right;
    int height;
};
int max(int a,int b){
    return a>b?a:b;
}
int getheight(avltree t)
{//树的深度
    if(t==null)
        return 0;
    else
    {
        int m=getheight(t->left);
        int n=getheight(t->right);
        if(m>n) return (m+1);
        else return (n+1);
    }
}
avltree singleleftrotation(avltree a){
    //a必须有一个左子结点b
    //将a与b做左单旋（ll），更新a与b的高度，返回新的根结点b
    avltree b = a->left;
    a->left = b->right;
    b->right = a;
    a->height = max(getheight(a->left),getheight(a->right))+1;
    b->height = max(getheight(b->left),a->height)+1;
    return b;
}
avltree singlerightrotation(avltree a){
    //a有右子结点b，rr
    avltree b = a->right;
    a->right = b->left;
    b->left = a;
    a->height = max(getheight(a->left),getheight(a->right))+1;
    b->height = max(getheight(b->right),a->height)+1;
    return b;
}

avltree doubleleftrightpotation(avltree a){
    //a有左子结点b，b有右结点c，lr旋转
    a->left = singlerightrotation(a->left);//bandc
    return singleleftrotation(a);//aandc ll
}

avltree doublerightleftpotation(avltree a){
    //rl
    a->right = singleleftrotation(a->right);
    return singlerightrotation(a);
}

//插入
avltree insert(avltree t,int x){
    if(!t){
        t = (avltree)malloc(sizeof(struct avlnode));
        t->data = x;
        t->height = 0;
        t->right = t->left = null;
    }
    else if(x < t->data){
        t->left = insert(t->left,x);
        if(getheight(t->left)-getheight(t->right) == 2)
            if(x<t->left->data)
                t = singleleftrotation(t);
            else
                t = doubleleftrightpotation(t);
    }
    else if(x > t->data){
        t->right = insert(t->right,x);
        if(getheight(t->left)-getheight(t->right) == -2)
            if(x > t->right->data)
                t = singlerightrotation(t);
            else
                t = doublerightleftpotation(t);
    }
    t->height = max(getheight(t->left),getheight(t->right))+1;
    return t;
}