定义

AVL树本质上是一颗二叉查找树，但是它又具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

插入与旋转

单旋

LL型

在根结点的左子树的左子树上插入节点。

RR型

在根结点的右子树的右子树上插入节点。

解决方法

双旋

LR型

在根结点的左子树的右子树上插入节点。

RL型

在根结点的右子树的左子树上插入节点。

解决方法

模板

#include <stdio.h>
#include <vector>
#include <string.h>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <stdlib.h>
using namespace std;
struct node
{
    int val;
    int high;
    node *left,*right;
    node(int x)
    {
        val=x;high=0;
        left=right=NULL;
    }
};
int gethigh(node *temp)
{
    if(temp==NULL)return -1;
    return temp->high;
}
node* SingleRotateLL(node *root)
{
    node *temp;
    temp=root->left;
    root->left=temp->right;
    temp->right=root;
    root->high=max(gethigh(root->left),gethigh(root->right))+1;     //更新高度
    temp->high=max(gethigh(temp->left),gethigh(temp->right))+1;     
    return temp;
}
node *SingleRotateRR(node *root)
{
    node *temp;
    temp=root->right;
    root->right=temp->left;
    temp->left=root;
    root->high=max(gethigh(root->left),gethigh(root->right))+1; //更新高度
    temp->high=max(gethigh(temp->left),gethigh(temp->right))+1;
    return temp;
}
node *DoubleRotateLR(node *root)
{
    root->left=SingleRotateRR(root->left);
    return SingleRotateLL(root);
}
node *DoubleRotateRL(node *root)
{
    root->right=SingleRotateLL(root->right);
    return SingleRotateRR(root);
}
node* Insert(node *root,int x)
{
    if(root==NULL){return new node(x);}
    if(x<root->val)
    {
        root->left=Insert(root->left,x);
        if(abs(gethigh(root->left)-gethigh(root->right))>1)
        {
            if(x<root->left->val)
                root=SingleRotateLL(root);
            else
                root=DoubleRotateLR(root);
        }
    }
    else
    {
        root->right=Insert(root->right,x);
        if (abs(gethigh(root->left)-gethigh(root->right))>1)
        {
            if(x>root->right->val)
                root=SingleRotateRR(root);
            else
                root=DoubleRotateRL(root);
        }
    }
    root->high=max(gethigh(root->left),gethigh(root->right))+1; //更新高度
    return root;
}
int main()
{
    int n,x;
    scanf("%d",&n);
    node *root=NULL;
    while(n--)
    {
        scanf("%d",&x);
        root=Insert(root,x);
    }
    printf("%d\n",root->val);
    return 0;
}