本文主要是介绍Treap总结与模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Treap
支持插入,删除,区间第k大,一个数的前驱,后继...
核心的思想:
每个节点有一个key表示该节点的值
和一个priority 表示当前节点的优先值
我们的树既满足二叉查找树的左小右大
右满足堆的上小下大
这样一来,均摊复杂度可以达到logn
在插入时,只要不满足堆的性质就旋转
在删除时,我们找到要删除的点,并将它旋转到叶子节点
在旋转时也要注意优先值
核心操作
rotate 旋转
type为0是右旋,1是左旋
void rotate(int &o,int type){int x=t[o].ch[type];t[o].ch[type]=t[x].ch[type^1];t[x].ch[type^1]=o; t[x].size=t[o].size;update_size(o);o=x;
}insert 插入
void insert(int &o,int val){if(o==0){o=++tot;t[o].size=t[o].num=1,t[o].key=val,t[o].p=randon();return;}t[o].size++;if(t[o].key==val){t[o].num++;return;}if(val<t[o].key){insert(t[o].ch[0],val);if(t[t[o].ch[0]].p<t[o].p)rotate(o,0);//右旋 }else{insert(t[o].ch[1],val);if(t[t[o].ch[1]].p<t[o].p)rotate(o,1);}
}erase 删除
void erase(int &o,int val){if(o==0) return;if(t[o].key==val){//转到叶子节点 if(t[o].num>1){t[o].num--;t[o].size--;return;}if(t[o].ch[0]==0) o=t[o].ch[1];else if(t[o].ch[1]==0) o=t[o].ch[0];else{if(t[t[o].ch[0]].p<t[t[o].ch[1]].p){rotate(o,0),erase(o,val);}else rotate(o,1),erase(o,val);}}else{if(val<t[o].key) t[o].size--,erase(t[o].ch[0],val); else t[o].size--,erase(t[o].ch[1],val);}
}查询排名
int rank_x(int o,int x){//x的排名 if(x==t[o].key) return t[t[o].ch[0]].size+1;else if(x<t[o].key){return rank_x(t[o].ch[0],x);}else return rank_x(t[o].ch[1],x)+t[t[o].ch[0]].size+t[o].num;
}
int rank_k(int o,int k){//查排名为k的 if(t[t[o].ch[0]].size>=k) return rank_k(t[o].ch[0],k);else if(t[t[o].ch[0]].size+t[o].num<k)return rank_k(t[o].ch[1],k-t[t[o].ch[0]].size-t[o].num);else return t[o].key;
}查询前驱后继
void pre(int o,int x){if(o==0) return;if(x>t[o].key){ans=o,pre(t[o].ch[1],x);}else pre(t[o].ch[0],x);
}
void suf(int o,int x){if(o==0) return;if(x<t[o].key){ans=o,suf(t[o].ch[0],x);}else suf(t[o].ch[1],x);
}答案为t[ans].key模板
#include<bits/stdc++.h>
#define N 100005
using namespace std;
struct Node{int ch[2],size,p,key,num;//priority
}t[N];
int n,root,ans,tot;
int read(){int cnt=0,f=1;char ch=0;while(!isdigit(ch)){ch=getchar();if(ch=='-')f=-1;}while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();return cnt*f;
}
inline int randon(){static int seed=233;return seed=int(seed*47821LL%2147483647);
}
void update_size(int o){t[o].size=t[o].num+t[t[o].ch[0]].size+t[t[o].ch[1]].size;
}
void rotate(int &o,int type){int x=t[o].ch[type];t[o].ch[type]=t[x].ch[type^1];t[x].ch[type^1]=o; t[x].size=t[o].size;update_size(o);o=x;
}
void insert(int &o,int val){if(o==0){o=++tot;t[o].size=t[o].num=1,t[o].key=val,t[o].p=randon();return;}t[o].size++;if(t[o].key==val){t[o].num++;return;}if(val<t[o].key){insert(t[o].ch[0],val);if(t[t[o].ch[0]].p<t[o].p)rotate(o,0);//右旋 }else{insert(t[o].ch[1],val);if(t[t[o].ch[1]].p<t[o].p)rotate(o,1);}
}
void erase(int &o,int val){if(o==0) return;if(t[o].key==val){//转到叶子节点 if(t[o].num>1){t[o].num--;t[o].size--;return;}if(t[o].ch[0]==0) o=t[o].ch[1];else if(t[o].ch[1]==0) o=t[o].ch[0];else{if(t[t[o].ch[0]].p<t[t[o].ch[1]].p){rotate(o,0),erase(o,val);}else rotate(o,1),erase(o,val);}}else{if(val<t[o].key) t[o].size--,erase(t[o].ch[0],val); else t[o].size--,erase(t[o].ch[1],val);}
}
int rank_x(int o,int x){//x的排名 if(x==t[o].key) return t[t[o].ch[0]].size+1;else if(x<t[o].key){return rank_x(t[o].ch[0],x);}else return rank_x(t[o].ch[1],x)+t[t[o].ch[0]].size+t[o].num;
}
int rank_k(int o,int k){//查排名为k的 if(t[t[o].ch[0]].size>=k) return rank_k(t[o].ch[0],k);else if(t[t[o].ch[0]].size+t[o].num<k)return rank_k(t[o].ch[1],k-t[t[o].ch[0]].size-t[o].num);else return t[o].key;
}
void pre(int o,int x){if(o==0) return;if(x>t[o].key){ans=o,pre(t[o].ch[1],x);}else pre(t[o].ch[0],x);
}
void suf(int o,int x){if(o==0) return;if(x<t[o].key){ans=o,suf(t[o].ch[0],x);}else suf(t[o].ch[1],x);
}
int main(){n=read();for(int i=1;i<=n;i++){int op=read(),x=read();if(op==1) insert(root,x);//插入xif(op==2) erase(root,x);if(op==3) printf("%d\n",rank_x(root,x));if(op==4) printf("%d\n",rank_k(root,x));if(op==5) pre(root,x),printf("%d\n",t[ans].key);if(op==6) suf(root,x),printf("%d\n",t[ans].key);}return 0;
}
这篇关于Treap总结与模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
