Root of AVL Tree (25)

图片参考：https://blog.csdn.net/apie_czx/article/details/48243549

#include<iostream>
using namespace std;
typedef struct node{
    int data;
    node *left,*right;
};
node *left(node *root){
    node *temp=root->right;
    root->right=temp->left;
    temp->left=root;
    return temp;
    
}
node *right(node *root){
    node *temp=root->left;
    root->left=temp->right;
    temp->right=root;
    return temp;
}
node *LeftRight(node *root){
    root->left=left(root->left);
    return right(root);
}
node *RightLeft(node *root){
    root->right=right(root->right);
    return left(root);
}
int getHeight(node* root){
    if(root==NULL) return 0;
    return max(getHeight(root->left),getHeight(root->right))+1;
}
node *insert(int data,node* root){
    if(root==NULL){
        root=new node();
        root->data=data;
        root->left=root->right=NULL;
    } 
    else if(root->data>data){
        root->left=insert(data,root->left);
        if(getHeight(root->left)-getHeight(root->right)==2)
            root=data<root->left->data?right(root):LeftRight(root);
    }else{
        root->right=insert(data,root->right);
        if((getHeight(root->left)-getHeight(root->right))==-2)
            root=data>root->right->data?left(root):RightLeft(root);
    }
    return root;
}
int main() {
    int n,data;
    cin>>n;
    node *root=NULL; 
    for(int i=0;i<n;i++){
        cin>>data;
        root=insert(data,root);
    }
    printf("%d",root->data);
}