Root of AVL Tree

平衡二叉树

模板题，但是更新高度容易忘记。

#include<bits/stdc++.h>
using namespace std;
struct node{
	node* left;
	node* right;
	int data,height;
};
int getHeight(node* root){
	if(root == NULL) return 0;
	return root->height; 
}
int getBalanceFactor(node* root){
	return getHeight(root->left) - getHeight(root->right);
}
void updateHeight(node* root){
	root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
}
void L(node* &root){ //左旋 
	node* tmp = root->right;
	root->right =  tmp->left;
	tmp->left = root;
	updateHeight(root);
	updateHeight(tmp);
	root = tmp;
}
void R(node* &root){ //左旋 
	node* tmp = root->left;
	root->left =  tmp->right;
	tmp->right = root;
	updateHeight(root);
	updateHeight(tmp);
	root = tmp;
}
void insert(node* &r, int v){
	if(r == NULL){
		r = new node;
		r->data = v;
		r->height = 1;
		r->left = r->right = NULL;
	}else if(v < r->data){ //左子树 
		insert(r->left,v);
		updateHeight(r);
		if(getBalanceFactor(r)==2){
			if(getBalanceFactor(r->left)== 1){ //LL型 
				R(r); 
			}else if(getBalanceFactor(r->left)==-1){ //LR型 
				L(r->left);
				R(r);
			}
		} 
	}else { //右子树 
		insert(r->right, v);
		updateHeight(r);
		if(getBalanceFactor(r)==-2){
			if(getBalanceFactor(r->right)==1){ //RL型 
				R(r->right);
				L(r);
			}else if(getBalanceFactor(r->right)==-1){//RR型
				L(r); 
			} 
		}
	}
}

int main(){
	int n,num;
	cin>>n;
	node* root = NULL;
	for(int i=0;i<n;i++){
		cin>>num;
		insert(root, num);
	}	
	cout<<root->data<<endl;
	return 0;
}