Treap详解

Treap=Tree+Heap

Treap中每个节点有2个值，其中一个满足二叉查找树的性质，一个满足大根堆的性质。把满足二叉查找树性质的值称作data，把满足大根堆性质的值称作value。 对于Treap来说，当前节点的data值大于左儿子，小于右儿子。当前节点的value值小于儿子节点的值。

每个节点的data我们无法改变，为了保证Treap的平衡性，我们需要让每个节点的value均为随机值，这样我们就可以保证这棵树“基本平衡”。

统计

\(up\)：计算儿子数

void up(int x){    t[x].siz=t[t[x].left].siz+t[t[x].right].siz+1;}

旋转

右旋就是，让当前节点降为自己的右儿子，让左儿子代替自己，并让自己左儿子的右儿子成为自己的左儿子。

左旋相反，让当前节点降为自己的左儿子，让右儿子代替自己，并让自己右儿子的左儿子成为自己的右儿子。

注：代码中的now加上了&是为了可以在函数中同时更改now的值。如上图右旋时，原来now指向\(A\)节点，运行完函数后指向\(B\)节点。

void right_rorate(int &now){    int tmp=t[now].left;    t[now].left=t[tmp].right;    t[tmp].right=now;    t[tmp].siz=t[now].siz;    up(now);    now=tmp;}void left_rorate(int &now){    int tmp=t[now].right;    t[now].right=t[tmp].left;    t[tmp].left=now;    t[tmp].siz=t[now].siz;    up(now);    now=tmp;}

旋转实例：

插入

给节点随机分配一个优先级(value)，先把要插入的点插入到一个叶子上，然后跟维护堆一样，我们维护一个 小根堆，如果当前节点的优先级比它的儿子大就旋转，如果当前节点是根的左儿子就右旋，如果当前节点是根的右儿子就左旋。

void insert(int &now,int data){    if(now==0)    {        now=++cnt;        t[now].siz=1;        t[now].data=data;        t[now].value=rand()*rand()%19620817;        return ;    }    t[now].siz++;    if(data>=t[now].data)    {        insert(t[now].right,data);    }    else    {        insert(t[now].left,data);    }    if(t[now].left!=0&&t[now].value>t[t[now].left].value)    {        right_rorate(now);    }    if(t[now].right!=0&&t[now].value>t[t[now].right].value)    {        left_rorate(now);    }    up(now);}

删除

因为\(Treap\)满足堆性质，所以只需要把要删除的节点旋转到叶节点上，然后直接删除就可以了。

具体的方法：

如果该节点的左子节点的优先级小于右子节点的优先级，右旋该节点，使该节点降为右子树的根节点，然后访问右子树的根节点，继续操作；

反之，左旋该节点,使该节点降为左子树的根节点，然后访问左子树的根节点，继续操作，直到变成可以直接删除的节点。

（即：让value的结点旋到上面，满足堆的性质）

void erase(int &now,int data){    t[now].siz--;    if(t[now].data==data)    {        if(t[now].left==0&&t[now].right==0)        {            now=0;            return ;        }        if(t[now].left==0||t[now].right==0)        {            now=t[now].left+t[now].right;            return ;        }        if(t[t[now].left].value
    
     =data)    {        erase(t[now].left,data);    }    else    {        erase(t[now].right,data);    }    up(now);}
    

查询排名

显然，若t[now].data<data，则在now的右子树中仍有部分小于data的数，所以在加上t[t[now].left].siz+1的同时还需在now的右子树中继续递归。反之，则只需在左子树中递归

int rank(int now,int data){    if(now==0)    {        return 0;    }    if(data>t[now].data)    {        return t[t[now].left].siz+1+rank(t[now].right,data);    }    return rank(t[now].left,data);}

查询排名为\(x\)的数

若左子树的大小刚好为\(x-1\)，则当前节点的data即为所求结果。

若左子树的大小大于\(x-1\)，则在右子树中递归查找。

若左子树的大小小于\(x-1\)，则在左子树中递归查找。

int find(int now,int rank){    if(rank==t[t[now].left].siz+1)    {        return t[now].data;    }    if(rank>t[t[now].left].siz+1)    {        return find(t[now].right,rank-t[t[now].left].siz-1);    }    return find(t[now].left,rank);}

查询前驱

函数定义：

int query_pre(int now,int data)

若now==0，则不存在返回值（return 0）。

若当前节点的值大于等于data，则在右子树中找。（必须包含等于！！！）

若当前节点的值小于data，则在左子树中找，若找不到，则返回当前节点的值。（不能有等于！！！）

int query_pre(int now,int data){    if(now==0)    {        return 0;    }    if(t[now].data>=data)    {        return query_pre(t[now].left,data);    }    int tmp=query_pre(t[now].right,data);    if(tmp==0)    {        return t[now].data;    }    return tmp;}

查询后继

与前驱几乎相同（略）

int query_suf(int now,int data){    if(now==0)    {        return 0;    }    if(t[now].data<=data)    {        return query_suf(t[now].right,data);    }    int tmp=query_suf(t[now].left,data);    if(tmp==0)    {        return t[now].data;    }    return tmp;}

完整代码：

#include
    
     using namespace std;struct Treap{    int data;    int value;    int left;    int right;    int siz;};Treap t[100005];int cnt;int root;void up(int x){    t[x].siz=t[t[x].left].siz+t[t[x].right].siz+1;}void right_rorate(int &now){    int tmp=t[now].left;    t[now].left=t[tmp].right;    t[tmp].right=now;    t[tmp].siz=t[now].siz;    up(now);    now=tmp;}void left_rorate(int &now){    int tmp=t[now].right;    t[now].right=t[tmp].left;    t[tmp].left=now;    t[tmp].siz=t[now].siz;    up(now);    now=tmp;}void insert(int &now,int data){    if(now==0)    {        now=++cnt;        t[now].siz=1;        t[now].data=data;        t[now].value=rand()*rand()%19620817;        return ;    }    t[now].siz++;    if(data>=t[now].data)    {        insert(t[now].right,data);    }    else    {        insert(t[now].left,data);    }    if(t[now].left!=0&&t[now].value>t[t[now].left].value)    {        right_rorate(now);    }    if(t[now].right!=0&&t[now].value>t[t[now].right].value)    {        left_rorate(now);    }    up(now);}void erase(int &now,int data){    t[now].siz--;    if(t[now].data==data)    {        if(t[now].left==0&&t[now].right==0)        {            now=0;            return ;        }        if(t[now].left==0||t[now].right==0)        {            now=t[now].left+t[now].right;            return ;        }        if(t[t[now].left].value
     
      =data)    {        erase(t[now].left,data);    }    else    {        erase(t[now].right,data);    }    up(now);}int rank(int now,int data){    if(now==0)    {        return 0;    }    if(data>t[now].data)    {        return t[t[now].left].siz+1+rank(t[now].right,data);    }    return rank(t[now].left,data);}int find(int now,int rank){    if(rank==t[t[now].left].siz+1)    {        return t[now].data;    }    if(rank>t[t[now].left].siz+1)    {        return find(t[now].right,rank-t[t[now].left].siz-1);    }    return find(t[now].left,rank);}int query_pre(int now,int data){    if(now==0)    {        return 0;    }    if(t[now].data>=data)    {        return query_pre(t[now].left,data);    }    int tmp=query_pre(t[now].right,data);    if(tmp==0)    {        return t[now].data;    }    return tmp;}int query_suf(int now,int data){    if(now==0)    {        return 0;    }    if(t[now].data<=data)    {        return query_suf(t[now].right,data);    }    int tmp=query_suf(t[now].left,data);    if(tmp==0)    {        return t[now].data;    }    return tmp;}int main(){    srand(19620817);    int n;    cin>>n;    int opt,data;    for(int i=1;i<=n;i++)    {        scanf("%d %d",&opt,&data);        if(opt==1)        {            insert(root,data);        }        if(opt==2)        {            erase(root,data);        }        if(opt==3)        {            printf("%d\n",rank(root,data)+1);        }        if(opt==4)        {            printf("%d\n",find(root,data));        }        if(opt==5)        {            printf("%d\n",query_pre(root,data));        }        if(opt==6)        {            printf("%d\n",query_suf(root,data));        }    }    return 0;}
     
    

注：本文部分图片来自（自己学的时候参考的）