AVL

struct node{
	int data;
	int height;
	node* lchild;
	node* rchild;
	node(int a):data(a),height(1),lchild(NULL),rchild(NULL){
	}
};

void create(int v){                                         //新建一个结点
	node* n=new node;
	n->data=v;
	n->height=1;
	n->lchild=NULL;
	n->rchild=NULL;
}

int getheight(node* root){                                 //获得树高
	if(root==NULL){
		return 0;
	}
	else{
		return root->height;
	}
}

int getBF(node* root){                                    //获得平衡因子
	return getheight(root->lchild)-getheight(root->rchild);
}

void updateheight(node* root){                            //更新树高
	root->height=max(getheight(root->lchild),getheight(root->rchild))+1;
}

void search(node* root,int x){                          //查找
	if(root==NULL){
		cout<<"Fail";
		return ;
	}
	if(root->data==x){
		cout<<root->data;
	}
	if(x>root->data){
		search(root->rchild,x);
	}
	else{
		serach(root->lchild,x);
	}
}

void L(node* & root){                                  //左旋
	node* temp=root->rchild;
	root->rchild=temp->lchild;
	temp->lchild=root;
	updateheight(root);
	updateheight(temp);
	root=temp;
}

void R(node* & root){                                 //右旋
	node* temp=root->lchild;
	root->lchild=temp->rchild;
	temp->rchild=root;
	updateheight(root);
	updateheight(temp);
	root=temp;
}

void Insert(node* & root,int x){                  //删除
	if(root==NULL){
		root=new node(x);
		return ;
	}
	if(x<root->data){
		Insert(root->lchild,x);
		updateheight(root);
		if(getBF(root)==2){
			if(getBF(root->lchild)==1){
				R(root);
			}
			if(getBF(root->child)==-1){
				L(root->lchild);
				R(root);
			}
		}
	}else{
		Insert(root->rchild,x);
		updateheight(root);
		if(getBF(root)==-2){
			if(getBF(root->rchild)==-1){
				L(root);
			}
			else(getBF(root->rchild==1)){
				R(root->rchild);
				L(root);
			}
		}
	}
}

node* create(int* a,int n){              //AVL树的创建
	node* root=NULL;
	for(int i=0;i<n;i++){
		Insert(root,a[i]);
	}
	return root;
}