本文是根据郭家宝的文章《Treap的原理及实现》写的。
#include<stdio.h> #include<string.h> #include<stdlib.h> struct node{ struct node *left,*right; int data,fix,size,weight; node(int x){ data=x; weight=size=1; fix=rand(); left=right=NULL; } void updata_size(){ size=weight+lsize()+rsize(); } int lsize(){return left?left->size:0;} int rsize(){return right?right->size:0;} }; void right_rotate(node* &p){//右旋 node* t=p->left; p->left=t->right; t->right=p; p->updata_size(); t->updata_size(); p=t; } void left_rotate(node* &p){//×óÐý node* t=p->right; p->right=t->left; t->left=p; p->updata_size(); t->updata_size(); p=t; } void insert(node* &p,int x){//左旋 if(p&&p->data==x){ p->weight++; p->size++; return ; } if(!p){ p=new node(x); }else if(x<p->data){ insert(p->left,x); if(p->left->fix<p->fix) right_rotate(p); }else{ insert(p->right,x); if(p->right->fix<p->fix) left_rotate(p); } p->updata_size(); } int find(node* p,int x){//查找 if(!p) return 0; if(p->data==x) return 1; if(p->data>x) return find(p->left,x); else return find(p->right,x); } void Delete(node* &p,int x){//删除 if(p->data==x){ if(--p->weight==0){ if(!p->left||!p->right){ node* t=p; if(!p->right) p=p->right; else p=p->left; delete p; }else{ if(p->left->fix<p->right->fix){ right_rotate(p); Delete(p->right,x); }else{ left_rotate(p); Delete(p->left,x); } } } }else if(p->data>x){ Delete(p->left,x); }else{ Delete(p->right,x); } if(p) p->updata_size(); } void mid_print(node* p){//中序 if(p){ mid_print(p->left); printf("%d ",p->data); mid_print(p->right); } } node* Pre(node* p,int x,node* opt){//前缀 if(!p) return opt; if(p->data<=x) return Pre(p->right,x,p); else return Pre(p->left,x,opt); } node* Suf(node* p,int x,node* opt){//后继 if(!p) return opt; if(p->data>=x) return Suf(p->left,x,p); else return Suf(p->right,x,opt); } node* Kth(node* p,int k){//Kth if(k<=p->lsize()) return Kth(p->left,k); else if(k>p->lsize()+p->weight) return Kth(p->right,k-(p->lsize()+p->weight)); else return p; } int rand(node* p,int x,int cur){//排名 if(x==p->data) return cur+p->lsize()+1; else if(x<p->data) return rand(p->left,x,cur); else return rand(p->right,x,cur+p->lsize()+p->weight); } int main(){ node* root; case 1:insert(root,x); case 2:if(find(root,x))Delete(root,x); case 3:mid_print(root); case 4:printf("%d ",Pre(root,x,0)->data); case 5:printf("%d ",Suf(root,x,0)->data); case 6:printf("%d ",Kth(root,k)->data); case 7:printf("%d ",rank(root,x)); return 0; }