avl有点繁杂，不好记。。
写了1h多。
#include<bits/stdc++.h>
using namespace std;
struct node{int data;int h;node *lchild;node *rchild;
};
node* newnode(int n){node *root=new node;root->h=1;root->data=n;root->lchild=NULL;root->rchild=NULL;return root;
}
int geth(node* root){if(root==NULL) return 0;else return root->h;
}
void hupdate(node *root){root->h=max(geth(root->lchild),geth(root->rchild))+1;
}
int BF(node* root){return geth(root->lchild)-geth(root->rchild);
}
void L(node* &root){node *temp=root->rchild;root->rchild=temp->lchild;temp->lchild=root;hupdate(root);hupdate(temp);root=temp;
}
void R(node* &root){node *temp=root->lchild;root->lchild=temp->rchild;temp->rchild=root;hupdate(root);hupdate(temp);root=temp;
}
void insert(node* &root,int n){if(root==NULL) {root=newnode(n);//printf("here");return;}if(n < root->data){insert(root->lchild,n);// printf("%d ",n);hupdate(root);if(BF(root)==2){if(BF(root->lchild)==1){R(root);}else if(BF(root->lchild)==-1){L(root->lchild);R(root);}}}else{insert(root->rchild,n);hupdate(root);if(BF(root)==-2){if(BF(root->rchild)==-1){L(root);}else if(BF(root->rchild)==1){R(root->rchild);L(root);}}}
}