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<t[t[now].right].value) { right_rorate(now); erase(t[now].right,data); return ; } else { left_rorate(now); erase(t[now].left,data); return ; } } if(t[now].data>=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; }
洛谷p3369完整代码:
#include<bits/stdc++.h> 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<t[t[now].right].value) { right_rorate(now); erase(t[now].right,data); return ; } else { left_rorate(now); erase(t[now].left,data); return ; } } if(t[now].data>=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("%dn",rank(root,data)+1); } if(opt==4) { printf("%dn",find(root,data)); } if(opt==5) { printf("%dn",query_pre(root,data)); } if(opt==6) { printf("%dn",query_suf(root,data)); } } return 0; }
注:c/c++开发分享Treap学习笔记部分图片来自brave_cattle的blog(自己学的时候参考的)
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605239.html