普通平衡树（treap）

题干：6种操作:

1. 插入x数

2. 删除x数(若有多个相同的数，因只删除一个)

3. 查询x数的排名(若有多个相同的数，因输出最小的排名)

4. 查询排名为x的数

5. 求x的前驱(前驱定义为小于x，且最大的数)

6. 求x的后继(后继定义为大于x，且最小的数)

一道treap板子题（splay也行）

下面是又长又持久的treap：

1.update

维护当前子树大小。

void update(int x)

{

    tr[x].size=tr[tr[x].ls].size+tr[tr[x].rs].size+tr[x].w;

}

2.旋转（lturn，rturn）

lturn（x）：把x转到原来的左儿子处。

rturn（x）：把x转到原来的有儿子处。

void lturn(int &x)

{

    int t = tr[x].rs;

    tr[x].rs=tr[t].ls;

    tr[t].ls=x;

    tr[t].size=tr[x].size;

    update(x);

    x=t;

}

void rturn(int &x)

{

    int t=tr[x].ls;

    tr[x].ls=tr[t].rs;

    tr[t].rs=x;

    tr[t].size=tr[x].size;

    update(x);

    x=t;

}

3.插入

插入一个点。具体步骤：

1.在最下面找到他。

2.加一个随机权值，扔进去。（随机权值目的：防止树退化成一条链，若退化则会将后面操作的时间复杂度从O(logn)变成O(n)。）

void insert(int &k , int x)

{

    if(k == )

    {

        cnt ++ ;

        k = cnt ;

        tr[k].size = tr[k].w =  ;

        tr[k].n1 = x ;

        tr[k].n2 = rand() ;

        return ;

    }

    tr[k].size ++ ;

    if(tr[k].n1 == x) tr[k].w ++ ;

    else if(x > tr[k].n1)

    {

        insert(tr[k].rs , x) ;

        if(tr[tr[k].rs].n2 < tr[k].n2) lturn(k) ;

    }else

    {

        insert(tr[k].ls , x) ;

        if(tr[tr[k].ls].n2 < tr[k].n2) rturn(k) ;

    }

}

如果不会随机数的话。。。https://www.cnblogs.com/LiGuanlin1124/p/9592229.html

4.删除

比插入复杂一点：

1.找到他。

2.分情况讨论：

{

　　（1）.只有一个儿子，则直接将其附成儿子。

　　（2）.儿女双全。选两个儿子中随机数rand值小的转上去，一直转到其满足（1）。（即将他儿子转没。）

　（3），没有儿子。残忍地return。

}

代码：

void del(int &k,int x)

{

    if(!k)return ;

    if(tr[k].n1==x)

    {

        if(tr[k].w>)

        {

            tr[k].size--;

            tr[k].w--;

            return ;

        }

        if(tr[k].ls*tr[k].rs==)

        {

            k=tr[k].ls+tr[k].rs;

        }else if(tr[tr[k].ls].n2<tr[tr[k].rs].n2)

        {

            rturn(k);

            del(k,x);

        }else

        {

            lturn(k);

            del(k,x);

        }

    }else if(tr[k].n1<x)

    {

        tr[k].size--;

        del(tr[k].rs,x);

    }else

    {

        tr[k].size--;

        del(tr[k].ls,x);

    }

}

5.查询排名，查询某排名是谁

难度小了很多，递归就行。

int pm(int k,int x)

{

    if(!k)return ;

    if(tr[k].n1==x)

    {

        return tr[tr[k].ls].size+;

    }

    if(tr[k].n1<x)

    {

        return tr[tr[k].ls].size+tr[k].w+pm(tr[k].rs,x);

    }else

    {

        return pm(tr[k].ls,x);

    }

}

int qp(int k,int x)//k子树内排名x的数

{

    if(!k)return ;

    if(x>tr[tr[k].ls].size&&x<=tr[tr[k].ls].size+tr[k].w)

    {

        return tr[k].n1;

    }else if(x<=tr[tr[k].ls].size)

    {

        return qp(tr[k].ls,x);

    }else

    {

        return qp(tr[k].rs,x-tr[tr[k].ls].size-tr[k].w);

    }

}

6.前驱后继

这是平衡树最普遍的用途了吧。

int ans;

void qq(int k,int x)

{

    if(!k)return ;

    if(tr[k].n1<x)

    {

        ans=k;

        qq(tr[k].rs,x);

    }else

    {

        qq(tr[k].ls,x);

    }

}

void hj(int k,int x)

{

    if(!k)return ;

    if(tr[k].n1>x)

    {

        ans=k;

        hj(tr[k].ls,x);

    }else

    {

        hj(tr[k].rs,x);

    }

}

巴特西

普通平衡树（treap）

最新文章

热门文章