fhq_treap学习笔记【平衡树】

作者: wjyyy 分类: Treap,学习笔记,数据结构 发布时间: 2018-08-08 22:06

点击量:30

 

    fhq_treap是一个比较好写,扩展性强,并且可以完成splay所有操作的常数不大的数据结构。

    fhq_treap不用旋转,它基于重构,也就是平衡树的合并和分裂。它可以通过一系列操作做到像splay一样分出一棵节点权值全部小于等于\(x\)的和一棵节点权值全部比\(x\)大的两棵树。它的思路是类似可持久化线段树,每次只基于一条链就可以重构出一棵新的并保持平衡的treap。

 

    分裂的过程就是沿着一条链,把小于\(x\)的元素(及其子树)加到左新树中,或把大于\(x\)的元素(及其子树)加到右新树中。并沿着一条更接近\(x\)的链递归处理。

 

    而合并的过程就是把两棵没有交集的一小一大的树,按照小根堆的原则,如果当前左边的子树权值较小,就把右边子树放在这个子树右面,递归下一层继续执行;如果右边子树权值较小,就把左边子树接在右边子树的左边,再递归执行。

 

    只要这样递归下去,就能完成分裂和合并的操作,一次分裂和合并,就是在重构这一棵treap了。

 

    对于普通平衡树一题的其他操作,可以通过分裂等操作方便地完成。实在不行也可以模拟splay的操作,因为这棵树依靠随机数保持平衡,总是趋近\(\log n\)的树高,因此每次模拟查询也是\(\log n\)的。

 

Code:

#include<cstdio>
#include<cstring>
#include<cstdlib>
struct node
{
    int key,rdm;
    int sz;
    node *ls,*rs;
    node(int key)
    {
        sz=1;
        this->key=key;
        rdm=rand();
        ls=NULL;
        rs=NULL;
    }
    int getsz()
    {
        if(!this)
            return 0;
        return sz;
    }
    void maintain()//维护操作
    {
        sz=ls->getsz()+1+rs->getsz();
    }
}*root;

node *Merge(node *a,node *b)
{
    if(!a||!b)
        return a?a:b;
    if(a->rdm<b->rdm)//小根堆
    {
        a->rs=Merge(a->rs,b);//把树b接到自己右儿子
        a->maintain();
        return a;
    }
    else
    {
        b->ls=Merge(a,b->ls);//把树a接到自己左儿子
        b->maintain();
        return b;
    }
}

void split(node *rt,int x,node *&a,node *&b)
{
    if(!rt)
    {
        a=NULL;
        b=NULL;
        return;
    }
    if(rt->key<=x)
    {
        split(rt->rs,x,rt->rs,b);
        a=rt;//把自己赋值给上面带下来的a
    }
    else
    {
        split(rt->ls,x,a,rt->ls);
        b=rt;
    }
    rt->maintain();
    return;
}

void Insert(node *&rt,int x)
{
    node *a,*b;
    split(rt,x,a,b);
    rt=Merge(Merge(a,new node(x)),b);
}

void Delete(node *&rt,int x)
{
    node *a,*b,*c;
    split(rt,x,a,b);
    split(a,x-1,a,c);
    if(c)
        c=Merge(c->ls,c->rs);
    rt=Merge(Merge(a,c),b);
}

int Rank(node *rt,int x)
{
    node *a,*b;
    split(rt,x-1,a,b);
    int ans=a->getsz()+1;
    rt=Merge(a,b);//做完要合并啊qwq
    return ans;
}

int kth(node *rt,int x)
{
    if(rt->ls->getsz()+1==x)
        return rt->key;
    if(rt->ls->getsz()>=x)//模拟splay
        return kth(rt->ls,x);
    return kth(rt->rs,x-rt->ls->getsz()-1);
}

int pre(node *rt,int x)
{
    node *a,*b;
    split(rt,x-1,a,b);//分裂就方便一些
    int ans=kth(a,a->getsz());
    rt=Merge(a,b);
    return ans;
}

int suc(node *rt,int x)
{
    node *a,*b;
    split(rt,x,a,b);
    int ans=kth(b,1);
    rt=Merge(a,b);
    return ans;
}

int main()
{
    int n,op,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&op,&x);
        if(op==1)
            Insert(root,x);
        else if(op==2)
            Delete(root,x);
        else if(op==3)
            printf("%d\n",Rank(root,x));
        else if(op==4)
            printf("%d\n",kth(root,x));
        else if(op==5)
            printf("%d\n",pre(root,x));
        else
            printf("%d\n",suc(root,x));
    }
    return 0;
}

 

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 【无旋(fhq)treap学习笔记】 注:这篇文章的写法是指针来着,目前比较适应数组写法 […]

/* */