缺少删除，见下一篇中的treap平衡树 特点：左大右小
代码
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #define M 99999 using namespace std; int lc[M],rc[M],size[M],key[M],f[M],tot=0; int n,m; int root=1; int add(int v) { tot++; size[tot]=1; key[tot]=v; return tot; } void insert(int &t,int v) { if(!t) t=add(v); else if(v<key[t]) insert(lc[t],v); else insert(rc[t],v); size[t]=size[lc[t]]+size[rc[t]]+1; } /*int askmin(int t,int k)//查询第k小 { if(size[lc[t]]==k-1) return key[t]; if(size[lc[t]]>k-1) return askmin(lc[t],k); else return askmin(rc[t],k-size[lc[t]]-1);//当前点是第size[lc[t]]+1大的值 }//与下面while版 askmin()等价 */ int askmin(int t,int k)//查找第k小的数 { int b=0; while(1){ if(size[lc[t]]==k-(1+b)) return key[t]; if(size[lc[t]]>k-1) t=lc[t]; else { b+=size[lc[t]]+1;// b累加 t=rc[t]; } } } /*int askxth(int t,int x)//查询x的排名 { if(key[t]==x) return size[lc[t]]+1; if(key[t]> x) return askxth(lc[t],x); if(key[t]< x) return askxth(rc[t],x)+size[lc[t]]+1; }//下面是 while 版 */ int askxth(int t,int x)//查询x的排名 { int b=0; while(1) { if(key[t]==x) break; if(key[t]>x) t=lc[t]; if(key[t]<x) { b+=size[lc[t]]+1;// b累加 t=rc[t]; } } return b+size[lc[t]]+1; } int askxup(int t,int x)//查询不小于x的最小值 { if(key[t]>=x&&(key[lc[t]]<x||!lc[t])) return key[t]; if(key[t]<x) return askxup(rc[t],x); else return askxup(lc[t],x); } int ask_front(int t,int x) { return askmin(t,askxth(t,x)-1); } int ask_behind(int t,int x) { return askmin(t,askxth(t,x)+1); } int main() { int p,x; scanf("%d",&n); scanf("%d%d",&p,&x); key[1]=x; tot++; for(int i=2;i<=n;i++) { scanf("%d%d",&p,&x); if(p==1) insert(root,x);//建树！ if(p==3) printf("%d\n",askmin(root,x));//查询第x小的数 if(p==4) printf("%d\n",askxth(root,x));//查询元素x的排名 if(p==5) printf("%d\n",askxup(root,x));//查询树中不小于数x的最小的数 if(p==6) printf("%d\n",ask_front(root,x));//查询元素x的前驱 if(p==7) printf("%d\n",ask_behind(root,x));//后继 } return 0; }