Treap学习笔记

# Treap详解 ## Treap=Tree+Heap Treap中每个节点有2个值，其中一个满足二叉查找树的性质，一个满足大根堆的性质。把满足二叉查找树性质的值称作```data```，把满足大根堆性质的值称作```value```。 对于Treap来说，当前节点的```data```值大于左儿子，小于右儿子。当前节点的```value```值小于儿子节点的值。 每个节点的```data```我们无法改变，为了保证Treap的平衡性，我们需要让每个节点的```value```均为随机值，这样我们就可以保证这棵树“基本平衡”。 ## 统计 $up$：计算儿子数 ``` cpp void up(int x) { t[x].siz=t[t[x].left].siz+t[t[x].right].siz+1; } ``` ## 旋转  右旋就是，让当前节点降为自己的右儿子，让左儿子代替自己，并让自己左儿子的右儿子成为自己的左儿子。 左旋相反，让当前节点降为自己的左儿子，让右儿子代替自己，并让自己右儿子的左儿子成为自己的右儿子。 注：代码中的```now```加上了```&```是为了可以在函数中同时更改```now```的值。如上图右旋时，原来```now```指向$A$节点，运行完函数后指向$B$节点。 ``` cpp 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```)，先把要插入的点插入到一个叶子上，然后跟维护堆一样，我们维护一个 **小根堆**，如果当前节点的优先级比它的儿子大就旋转，**如果当前节点是根的左儿子就右旋，如果当前节点是根的右儿子就左旋。** ``` cpp 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```的结点旋到上面，满足堆的性质） ``` cpp 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```的右子树中继续递归。反之，则只需在左子树中递归 ``` cpp 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$，则在左子树中递归查找。 ``` cpp 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); } ``` ## 查询前驱 函数定义： ``` cpp int query_pre(int now,int data) ``` 若```now==0```，则不存在返回值（```return 0```）。 若当前节点的值大于等于```data```，则在左子树中找。（必须包含等于！！！） 若当前节点的值小于```data```，则在右子树中找，若找不到，则返回当前节点的值。（不能有等于！！！） ``` cpp 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; } ``` ## 查询后继 与前驱几乎相同（略） ``` cpp 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](https://www.luogu.org/problemnew/show/P3369)完整代码： ``` cpp #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("%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; } ``` 注：本文部分图片来自[Brave_Cattle的Blog](https://www.cnblogs.com/BCOI/p/9072444.html)（自己学的时候参考的）