注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

平衡树系列专题之一:Treap  

2014-04-04 08:58:00|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Treap似乎没有中文名字= =(也许是树堆?)。Treap是一棵拥有两个值域(键值及优先级)的BST,对于键值,Treap是一棵BST,对于优先级,Treap是一个堆(从名字可以看出来,Treap=Tree+heap)。可以证明,如果每个节点的优先级各不相同,整棵树就可以唯一确定。我们给每个节点的优先级随机设一个值,可以证明每次操作的期望复杂度是O(log2N)的(当然如果你rp够差,那也会变成一条链= =,不过那样的概率跟你被雷劈中差不多了= =)

平衡树系列专题之一:Treap - mxh1999 - 一个蒟蒻的代码回收站

放上Treap的每个节点的结构体函数

struct node

{

    node *left,*right;

    int r,v,s,num;//r表示优先级,v表示键值,s表示以它为子树的节点个数,num表示键值为v的个数

    node(int x)

    {

        left=right=NULL;

        v=x;

        r=rand();

        s=1;

        num=1;

    }

    bool operator < (const node &rhs) const

    {

        return r < rhs.r;

    }

    int cmp(int x) const

    {

        if (x==v) return -1;

        return x<v ? 0 : 1;

    }

    void maintain()

    {

        s=num;

        if (left!=NULL) s+= left->s;

        if (right!=NULL) s+= right->s;

    }

};

插入时,先像BST一样插入,然后判断,如果不符合堆的性质就旋转。

详见代码


删除时,先找到要删除的点,如果它是叶子节点,直接删,如果它只有一棵子树,把它的子树代替它的位置。

如果有两颗子树,则把优先级比较高的一棵旋转到根(此时要删除的点跑到了另一棵子树里),然后递归删除另一棵子树中的该节点。

详见代码


剩下的就是平衡树的基本操作了


求k大(小):

先访问根,如果整棵树都没有k个节点,直接返回没找到。

对于一个节点,设q=它的左子树的节点个数+1;

如果q>k-1,则访问左子树;

如果q=k-1,则返回当前节点;

如果q<k-1,则k减去q,并访问右子树。

求某个数的排名:

跟求第k大差不多,详细请见代码。

求前驱:

访问根,如果根的值小于它,则更新答案,并访问右子树,否则访问左子树,重复该过程,直到访问到空节点为止。

求后继:

跟求前驱差不多。

于是,一棵Treap就写完了。


放上完整代码:

#include<cstdlib>

#include<cstdio>

#include<iostream>

using namespace std;

 

#define INF 1<<30

struct node

{

    node *left,*right;

    int r,v,s,num;

    node(int x)

    {

        left=right=NULL;

        v=x;

        r=rand();

        s=1;

        num=1;

    }

    bool operator < (const node &rhs) const

    {

        return r < rhs.r;

    }

    int cmp(int x) const

    {

        if (x==v) return -1;

        return x<v ? 0 : 1;

    }

    void maintain()

    {

        s=num;

        if (left!=NULL) s+= left->s;

        if (right!=NULL) s+= right->s;

    }

};

 

struct Treap

{

    node* root;

    Treap()

    {

        root=NULL;

    }

    void left_rotate(node* &o) //左旋

    {

        node* k=o->right;

        o->right=k->left;

        k->left=o;

        o->maintain();

        k->maintain();

        o=k;

    }

    void right_rotate(node* &o) //右旋

    {

        node* k=o->left;

        o->left=k->right;

        k->right=o;

        o->maintain();

        k->maintain();

        o=k;

    }

    void insert(node* &o,int x) //插入

    {

        if (o==NULL)

        {

            o=new node(x);

        } else

        {

            int tmp=o->cmp(x);

            if (tmp==-1)

            {

                o->num++;

                o->maintain();

            }

            if (tmp==0)

            {

                insert(o->left,x);

                if (o->left > o) right_rotate(o);

                o->maintain();

            }

            if (tmp==1)

            {

                insert(o->right,x);

                if (o->right > o) left_rotate(o);

                o->maintain();

            }

        }

    }

    void remove(node* &o,int x) //删除

    {

        int d=o->cmp(x);

        if (d==-1)

        {

            if (o->num > 1)

            {

                o->num--;

                o->maintain();

                return;

            }

            if (o->left == NULL)

            {

                o=o->right;

                return;

            }

            if (o->right == NULL)

            {

                o=o->left;

                return;

            }

            int d1=(o->left > o->right) ? 1 : 0;

            if (d1==0)

            {

                left_rotate(o);

                remove(o->left,x);

                o->maintain();

            }

            if (d1==1)

            {

                right_rotate(o);

                remove(o->right,x);

                o->maintain();

            }

        } else

        {

            if (d==0) remove(o->left,x);

            if (d==1) remove(o->right,x);

            o->maintain();

        }

    }

    int find_x(node* o,int x) //询问某数的排名

    {

        int ans=0;

        while (o!=NULL)

        {

            int d=o->cmp(x);

            if (d==-1)

            {

                if (o->left!=NULL) ans+=o->left->s;

                ans++;

                return ans;

            }

            if (d==0)

            {

                o=o->left;

            }

            if (d==1)

            {

                if (o->left!=NULL) ans+=o->left->s;

                ans+=o->num;

                o=o->right;

            }

        }

        return 0;

    }

    int find_k(node* o,int k) //询问第k大

    {

        while (o!=NULL)

        {

            int d=0;

            if (o->left!=NULL) d=o->left->s;

            if (k>d && k<=d+o->num) return o->v;

            if (k<=d)

            {

                o=o->left;

            }

            if (k>d+o->num)

            {

                k-=d+o->num;

                o=o->right;

            }

        }

    }

    int prev(int x) //求前驱

    {

        node* tmp=root;

        if (tmp==NULL) return INF;

        int ans=-INF;

        while (tmp!=NULL)

        {

            if (tmp->v < x)

            {

                ans=max(ans,tmp->v);

                tmp=tmp->right;

            } else

            {

                tmp=tmp->left;

            }

        }

        if (ans==-INF) return INF;

        else return ans;

    }

    int next(int x) //求后继

    {

        node* tmp=root;

        if (tmp==NULL) return -INF;

        int ans=INF;

        while (tmp!=NULL)

        {

            if (tmp->v > x)

            {

                ans=min(ans,tmp->v);

                tmp=tmp->left;

            } else

            {

                tmp=tmp->right;

            }

        }

        if (ans==INF) return -INF;

        else return ans;

    }

} treap;


  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018