#include<iostream>
using namespace std;
struct node
{
	int val;
	struct node* left;
	struct node* right;
};
//LL旋转
node* singleLeftRotation(node *root)
{
	node* t=root->left;
	root->left=t->right;
	t->right=root;
	return t;
}
//RR旋转
node* singleRightRotation(node *root)
{
	node* t=root->right;
	root->right=t->left;
	t->left=root;
	return t;
}
//LR旋转
node* doubleLsftRightRotation(node* root)
{
	root->left=singleRightRotation(root->left);
	return singleLeftRotation(root);
}
//RL旋转
node *doubleRightLeftRotation(node *root){
    root->right=singleLeftRotation(root->right);
    return singleRightRotation(root);
}
//高度检测
int getHeight(node *root){
    if(root==NULL) return 0;
    return max(getHeight(root->left),getHeight(root->right))+1;
}
//平衡树插入
node *insert(node *root,int val){
    if(root==NULL){//为空就新建
        root=new node();
        root->val=val;
        root->left=NULL;
        root->right=NULL;
    }else if(val<root->val){
        root->left=insert(root->left,val);
        if(getHeight(root->left)-getHeight(root->right)==2)//如果比左结点还小就用LL旋转，反之用LR旋转
            root=val<root->left->val ? singleLeftRotation(root):doubleLeftRightRotation(root);
    }else{
        root->right=insert(root->right,val);
        if(getHeight(root->left)-getHeight(root->right)==-2)//相应的右子树也是用RR或者RL
            root=val>root->right->val ? singleRightRotation(root):doubleRightLeftRotation(root);
    }
    return root;
}