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（自己学的时候参考的）