AVL树笔记(一):zig-zag,insert,find,predecessor,successor

AVL树就是一棵平衡的二叉查找树。
其维护平衡的方式是:维护一个平衡因子h,即子树高度,如果左子树高度和右子树高度相差2,那么就旋转把它弄平衡。
《AVL树笔记(一):zig-zag,insert,find,predecessor,successor》
这个二叉树明显不平衡,可以发现全部左偏,于是右旋。
右旋就是当前节点的左儿子 的 右儿子是当前节点。
如果当前节点有右儿子,怎么办?
那么把这个右儿子拆下来然后装在当前节点的左儿子上。
如图:
《AVL树笔记(一):zig-zag,insert,find,predecessor,successor》

《AVL树笔记(一):zig-zag,insert,find,predecessor,successor》
这个二叉树明显不平衡,可以发现全部右偏,于是左旋。
左旋就是当前节点的右儿子 的 左儿子是当前节点。
如果当前节点有左儿子,怎么办?
那么把这个左儿子拆下来然后装在当前节点的右儿子上。
这个不给图了。
《AVL树笔记(一):zig-zag,insert,find,predecessor,successor》
这个二叉树明显不平衡,下面右偏上面左偏,于是先左旋再右旋。
《AVL树笔记(一):zig-zag,insert,find,predecessor,successor》
这个二叉树明显不平衡,下面左偏上面右偏,于是先右旋再左旋。
说白了就是全部反着来,是不是很好懂?
旋转完了,然后insert。
insert就是先插入进去,然后如果不平衡就旋转一下,就平衡了。
顺便更新h。
insert完了,然后find,predecessor,successor。
find,predecessor,successor就和二叉查找树一样。
明天讲讲delete。
附代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct node{
    int h,v,lc,rc;
}tree[40010];
int cnt,ans,n,val,pred,succ,rt;
int abs(int x)
{
    return x<0?-x:x;
}
int zig(int r)
{
    int t=tree[r].lc;
    tree[r].lc=tree[t].rc;
    tree[t].rc=r;
    tree[r].h=max(tree[tree[r].lc].h,tree[tree[r].rc].h)+1;
    tree[t].h=max(tree[tree[t].lc].h,tree[tree[t].rc].h)+1;
    return t;
}
int zag(int r)
{
    int t=tree[r].rc;
    tree[r].rc=tree[t].lc;
    tree[t].lc=r;
    tree[r].h=max(tree[tree[r].lc].h,tree[tree[r].rc].h)+1;
    tree[t].h=max(tree[tree[t].lc].h,tree[tree[t].rc].h)+1;
    return t;
}
int zigzag(int r)
{
    tree[r].rc=zig(tree[r].rc);
    return zag(r);
}
int zagzig(int r)
{
    tree[r].lc=zag(tree[r].lc);
    return zig(r);
}
int insert(int r,int x)
{
    if(r==0)
    {
        tree[++cnt].v=x;
        tree[cnt].h=1;
        return cnt;
    }
    if(x<tree[r].v)
    {
        tree[r].lc=insert(tree[r].lc,x);
        if(tree[tree[r].lc].h==tree[tree[r].rc].h+2)
        {
            if(x<tree[tree[r].lc].v)r=zig(r);
            else if(x>tree[tree[r].lc].v)r=zagzig(r);
        }
    }
    else if(x>tree[r].v)
    {
        tree[r].rc=insert(tree[r].rc,x);
        if(tree[tree[r].rc].h==tree[tree[r].lc].h+2)
        {
            if(x>tree[tree[r].rc].v)r=zag(r);
            else if(x<tree[tree[r].rc].v)r=zigzag(r);
        }
    }
    tree[r].h=max(tree[tree[r].lc].h,tree[tree[r].rc].h)+1;
    return r;
}
bool find(int r,int x)
{
    if(r==0)return 0;
    if(tree[r].v==x)return 1;
    if(tree[r].v<x)return find(tree[r].rc,x);
    if(tree[r].v>x)return find(tree[r].lc,x);
}
void predecessor(int r,int x)
{
    if(r==0)return;
    if(tree[r].v<x)
    {
        pred=tree[r].v;
        predecessor(tree[r].rc,x);
    }
    else predecessor(tree[r].lc,x);
}
void successor(int r,int x)
{
    if(r==0)return;
    if(tree[r].v>x)
    {
        succ=tree[r].v;
        successor(tree[r].lc,x);
    }
    else successor(tree[r].rc,x);
}
int main()
{
    scanf("%d%d",&n,&ans);
    rt=insert(rt,-99999999);
    rt=insert(rt,99999999);
    rt=insert(rt,ans);
    for(int i=1;i<n;++i)
    {
        scanf("%d",&val);
        if(find(rt,val))continue;
        pred=succ=0;
        predecessor(rt,val);
        successor(rt,val);
        ans+=min(abs(pred-val),abs(succ-val));
        rt=insert(rt,val);
    }
    printf("%d\n",ans);
}

这个题是BZOJ1588(HNOI2002)就是求前驱后继的裸题。

    原文作者:AVL树
    原文地址: https://blog.csdn.net/quack_quack/article/details/49873159
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞