二叉搜索树的插入、查找、删除等操作的效率与树高成正比，因此在创建二叉搜索树时要尽可能地通过调平衡压缩树高。平衡树有很多种，例如AVL树、Treap、伸展树（Splay）、SBT、红黑树等。
Treap简介
特点与作用
Treap，即Tree+Heap，又叫做树堆，它同时满足了二叉搜索树和堆两种性质。二叉搜索树满足中序有序性，输入的序列不同，创建的二叉搜索树也不同，在最坏的情况下（比如只有左子树或者只有右子树），会退化为线性。
若一个二叉搜索树插入的节点顺序时随机的，则得到的二叉搜索树在大多情况下是平衡的，即使存在一些极端的情况但这种情况发生的概率很小，因此以随机顺序创建的二叉搜索树，其期望高度为
基本结构
Treap是一种平衡二叉树，它给每个节点都附加了一个随机数，使其满足堆的性质，而节点的值又满足二叉搜索树的有序性，其基本操作的期望时间复杂度为
在Treap构建过程中，插入节点时会给每个节点都附加一个随机数作为优先级，该优先级满足堆的性质（最大堆或者最小堆均可，本文以最大堆为例，根的优先级大于左右子树的节点），数值满足二叉搜索树的性质（中序有序性，左子树大于根，右子树小于根）。
Treap操作
左旋和右旋
Treap需要两种操作：左旋和右旋。
- 右旋（
）：节点 右旋时，会携带自己的右子树，向右旋转到 的右子树位置， 的右子树被抛弃，此时 右旋后左子树正好空闲，将 的右子树放在 的左子树位置，旋转后的树根为 。 - 左旋（
）：节点 左旋时，会携带自己的左子树，向左旋转到 的左子树位置， 的左子树被抛弃，此时 左旋后右子树正好空闲，将 的左子树放在 的右子树位置，旋转后的树根为 。
所以，无论是左旋还是右旋，旋转后总有一棵子树被抛弃，一个指针空闲，正好配对。
右旋代码：
inline void zig(reg int &p){ reg int q=tree[p].lc; tree[p].lc=tree[q].rc; tree[q].rc=p; tree[q].size=tree[p].size; Update(p); p=q; return;}左旋代码：
inline void zag(reg int &p){ reg int q=tree[p].rc; tree[p].rc=tree[q].lc; tree[q].lc=p; tree[q].size=tree[p].size; Update(p); p=q; return;}左旋右旋后，节点所对应的子树大小也会发生变化，需要更新每个节点更新后所对应的子树个数
更新子树大小代码：
inline void Update(reg int p){ tree[p].size=tree[tree[p].lc].size+tree[tree[p].rc].size+tree[p].num; return;}插入
Treap的插入操作与二叉搜索树一样，首先根据有序性找到插入的位置，然后创建节点插入该位置。其中每个点都会有一个随机值，该值为优先级，会自下向上检查这一棵树是否满足堆的性质，若不满足会进行左旋或者右旋的操作。
新建节点代码：
inline int New(reg int val){ tree[++cnt].val=val; tree[cnt].pri=rand(); tree[cnt].num=tree[cnt].size=1; tree[cnt].rc=tree[cnt].lc=0; return cnt;}当我们要插入一个数时，从根节点
- 如果
的值小于当前节点 的值，就在它的左子树递归插入。回溯的时候根据优先级进行左旋或者右旋。 - 如果
的值大于当前节点 的值，就在它的右子树递归插入。回溯的时候根据优先级进行左旋或者右旋。 - 如果
的值等于当前节点 的值，就将当前节点的 的值加一，在这里 表示相同元素的数量。如果只要保留不重复的元素就什么也不做。
插入代码：
inline void Insert(reg int &p,reg int val){ if(!p) { p=New(val); return; } tree[p].size++; if(val==tree[p].val) { tree[p].num++; return; } else if(val<tree[p].val) { Insert(tree[p].lc,val); if(tree[p].pri<tree[tree[p].lc].pri) zig(p); } else { Insert(tree[p].rc,val); if(tree[p].pri<tree[tree[p].rc].pri) zag(p); } return;}删除
首先找到删除的节点，将该节点向优先级大的子节点旋转，一直旋转到叶子，最后删除叶子。
具体来说，我们要删除一个元素
- 如果
的值小于当前节点 的值，则在 的左子树中递归删除。 - 如果
的值大于当前节点 的值，则在 的右子树中递归删除。 - 如果
的值等与当前节点 的值，则： - 若当前节点
只有左子树或者是右子树，就将当前节点 赋值为其儿子的状态，。 - 若当前节点
左儿子的优先级大于右儿子的优先级，则 左旋。继续在右子树中递归删除。 - 若当前节点
左儿子的优先级小于右儿子的优先级，则 右旋。继续在左子树中递归删除。
- 若当前节点
代码：
inline void Delete(reg int &p,reg int val){ if(!p) return; tree[p].size--; if(val==tree[p].val) { if(tree[p].num>1) { tree[p].num--; return; } if(!tree[p].lc||!tree[p].rc) p=tree[p].lc+tree[p].rc; else if(tree[tree[p].lc].pri>tree[tree[p].rc].pri) { zig(p); Delete(tree[p].rc,val); } else { zag(p); Delete(tree[p].lc,val); } return; } if(val<tree[p].val) Delete(tree[p].lc,val); else Delete(tree[p].rc,val); return;}前驱与后继
首先理解什么是前驱、后继：
-
前驱结点：节点
值小于该节点 值并且值最大的节点 -
后继节点：节点
值大于该节点 值并且值最小的节点
在Treap中求一个节点
在Treap中求一个节点
求前驱代码：
inline int GetPre(reg int val){ reg int p=rt; reg int res=0; while(p) { if(tree[p].val<val) { res=tree[p].val; p=tree[p].rc; } else p=tree[p].lc; } return res;}求后继代码：
inline int GetNext(reg int val){ reg int p=rt; reg int res=0; while(p) { if(tree[p].val>val) { res=tree[p].val; p=tree[p].lc; } else p=tree[p].rc; } return res;}根据
从树根出发，如果当前要查找的
代码：
inline int GetRankByVal(reg int p,reg int val){ if(!p) return 1; if(tree[p].val==val) return tree[tree[p].lc].size+1; if(val<tree[p].val) return GetRankByVal(tree[p].lc,val); else return GetRankByVal(tree[p].rc,val)+tree[tree[p].lc].size+tree[p].num;
}根据排名查找
从树根出发，如果当前要查找的排名
代码：
inline int GetValByRank(reg int p,reg int rank){ if(!p) return 0; if(tree[tree[p].lc].size>=rank) return GetValByRank(tree[p].lc,rank); if(tree[tree[p].lc].size+tree[p].num>=rank) return tree[p].val; return GetValByRank(tree[p].rc,rank-tree[tree[p].lc].size-tree[p].num);}代码
来源：洛谷：P3369 【模板】普通平衡树、洛谷：P6136 【模板】普通平衡树（数据加强版）
#include<iostream>#include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>#include<cmath>#include<vector>#include<queue>#include<map>#include<set>#include<ctime>using namespace std;#define LL long long#define uLL unsigned long long#define reg register#define PI acos(-1.0)#define pb(x) push_back(x)#define mp(a,b) make_pair(a,b)#define fi first#define se second#define pr(x) cerr<<#x<<"="<<(x)<<endl#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}#define inf 100000000#define N 1000#define M 4000001template<class T>inline void read(T &x){ x=0;register char c=getchar();register bool f=0; while(!isdigit(c))f^=c=='-',c=getchar(); while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar(); if(f)x=-x;}template<class T>inline void print(T x){ if(x<0)putchar('-'),x=-x; if(x>9)print(x/10); putchar('0'+x%10);}struct Node{ int lc,rc,val,pri,num,size;}tree[M];int cnt,rt,n,m,Last,ans;inline int New(reg int val){ tree[++cnt].val=val; tree[cnt].pri=rand(); tree[cnt].num=tree[cnt].size=1; tree[cnt].rc=tree[cnt].lc=0; return cnt;}inline void Update(reg int p){ tree[p].size=tree[tree[p].lc].size+tree[tree[p].rc].size+tree[p].num; return;}inline void zig(reg int &p){ reg int q=tree[p].lc; tree[p].lc=tree[q].rc; tree[q].rc=p; tree[q].size=tree[p].size; Update(p); p=q; return;}inline void zag(reg int &p){ reg int q=tree[p].rc; tree[p].rc=tree[q].lc; tree[q].lc=p; tree[q].size=tree[p].size; Update(p); p=q; return;}inline void Insert(reg int &p,reg int val){ if(!p) { p=New(val); return; } tree[p].size++; if(val==tree[p].val) { tree[p].num++; return; } else if(val<tree[p].val) { Insert(tree[p].lc,val); if(tree[p].pri<tree[tree[p].lc].pri) zig(p); } else { Insert(tree[p].rc,val); if(tree[p].pri<tree[tree[p].rc].pri) zag(p); } return;}inline void Delete(reg int &p,reg int val){ if(!p) return; tree[p].size--; if(val==tree[p].val) { if(tree[p].num>1) { tree[p].num--; return; } if(!tree[p].lc||!tree[p].rc) p=tree[p].lc+tree[p].rc; else if(tree[tree[p].lc].pri>tree[tree[p].rc].pri) { zig(p); Delete(tree[p].rc,val); } else { zag(p); Delete(tree[p].lc,val); } return; } if(val<tree[p].val) Delete(tree[p].lc,val); else Delete(tree[p].rc,val); return;}inline int GetPre(reg int val){ reg int p=rt; reg int res=0; while(p) { if(tree[p].val<val) { res=tree[p].val; p=tree[p].rc; } else p=tree[p].lc; } return res;}inline int GetNext(reg int val){ reg int p=rt; reg int res=0; while(p) { if(tree[p].val>val) { res=tree[p].val; p=tree[p].lc; } else p=tree[p].rc; } return res;}inline int GetRankByVal(reg int p,reg int val){ if(!p) return 1; if(tree[p].val==val) return tree[tree[p].lc].size+1; if(val<tree[p].val) return GetRankByVal(tree[p].lc,val); else return GetRankByVal(tree[p].rc,val)+tree[tree[p].lc].size+tree[p].num;
}inline int GetValByRank(reg int p,reg int rank){ if(!p) return 0; if(tree[tree[p].lc].size>=rank) return GetValByRank(tree[p].lc,rank); if(tree[tree[p].lc].size+tree[p].num>=rank) return tree[p].val; return GetValByRank(tree[p].rc,rank-tree[tree[p].lc].size-tree[p].num);}int main(){ srand(time(NULL)); read(n),read(m); for(int i=1;i<=n;i++) { reg int a; read(a); Insert(rt,a); } for(reg int i=1;i<=m;i++) { reg int opt,x; read(opt),read(x); x^=Last; if(opt==1) Insert(rt,x); else if(opt==2) Delete(rt,x); else if(opt==3) {Last=GetRankByVal(rt,x);ans^=Last;} else if(opt==4) {Last=GetValByRank(rt,x);ans^=Last;} else if(opt==5) {Last=GetPre(x);ans^=Last;} else if(opt==6) {Last=GetNext(x);ans^=Last;} } printf("%d",ans); return 0;}