二叉平衡树（AVL）的插入

这次节点的数据域增加了高度这个量，用来计算平衡因子，以此在插入的时候来调整树的结构
节点：

struct node
{
    int val;
    int hei;
    node *l;
    node *r;
};

构造新节点

node* newNode(int v)
{
    node* Node=new node;
    Node->val=v;
    Node->hei=1;
    Node->l=Node->r=NULL;
    return Node;
}

获取树高

int getHeight(node* root)
{
    if(root==NULL)
        return 0;
    return root->hei;
}

计算平衡因子：

int getBalanceFactor(node* root)
{
    return getHeight(root->l)-getHeight(root->r);
}

更新树高：

void updateHeight(node* root)
{
    root->hei=max(getHeight(root->l),getHeight(root->r))+1;
}

左旋操作：

void L(node* &root)
{
    node* temp=root->r;
    root->r=temp->l;
    temp->l=root;
    updateHeight(root);
    updateHeight(temp);
    root=temp;
}

右旋操作（与左旋对称）：

void R(node* &root)
{
    node* temp=root->l;
    root->l=temp->r;
    temp->r=root;
    updateHeight(root);
    updateHeight(temp);
    root=temp; 
}

插入：

void insert(node* &root,int v)
{
    if(root==NULL)
    {
        root=newNode(v);
        return;
    }
    if(v<root->val)
    {
        insert(root->l,v);
        updateHeight(root);
        if(getBalanceFactor(root)==2)
            if(getBalanceFactor(root->l)==1)
                R(root);
            else
            {
                L(root->l);
                R(root);
            }   
    }
    else
    {
        insert(root->r,v);
        updateHeight(root);
        if(getBalanceFactor(root)==-2)
            if(getBalanceFactor(root->r)==-1)
                L(root);
            else
            {
                R(root->r);
                L(root);
            }
    }
}

关键小心左旋右旋和插入的细节。