平衡二叉树（AVL）

avl就是优化二叉查找树

平衡因子不大于1

左 < 根 < 右

 

具体看代码

#include<bits/stdc++.h>

using namespace std;
typedef struct node;
typedef node * tree;
struct node
{
    int v;
    int heigh;
    tree l,r;
};

//获取以root为根结点的子树的当前height
int getheigh(tree root)
{
    if(root==null) return 0;
    return root->heigh;
}

//更新结点root的heigh
void updataheigh(tree root)
{
    //max(左孩子结点的height,有孩子结点的height)+1
    root->heigh=max(getheigh(root->l),getheigh(root->r))+1;
}


//计算平衡因子
int getbalance(tree root)
{
    //左-右
    return getheigh(root->l)-getheigh(root->r);
}


//左旋  注意原理 对于rr是root的右孩子的平衡因子是-1
void l(tree &root)
{
    tree temp;
    temp=root->r;
    root->r=temp->l;
    temp->l=root;
    updataheigh(root);
    updataheigh(temp);
    root=temp;
}

void r(tree &root)
{
    tree temp;
    temp=root->l;
    root->l=temp->r;
    temp->r=root;
    updataheigh(root);
    updataheigh(temp);
    root=temp;
}
void insertt(tree &root,int v)
{
    if(root==null){//当结点是空的时候 就是插入的时候
        root=new node;
        root->v=v;
        root->heigh=1;
        root->l=root->r=null;
        return;
    }
    if(v<root->v){
        insertt(root->l,v);
        updataheigh(root);//注意更新树高
        if(getbalance(root)==2){
            if(getbalance(root->l)==1){
                r(root);
            }
            else if(getbalance(root->l)==-1){
                l(root->l);
                r(root);
            }
        }
    }
    else{
        insertt(root->r,v);
        updataheigh(root);
        if(getbalance(root)==-2){
            if(getbalance(root->r)==-1){
                l(root);
            }
            else if(getbalance(root->r)==1){
                r(root->r);
                l(root);
            }
        }
    }

}
int main()
{
    int n;
    scanf("%d",&n);
    int x;
    tree root;
    root=null;
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        insertt(root,x);
    }
    printf("%d\n",root->v);
    return 0;
}