平衡树treap的基本操作-白红宇

平衡树treap的基本操作

阅读量：4954 次

发布时间：2019-06-12

本文共 1780 字，大约阅读时间需要 5 分钟。

也是一棵平衡树所以要旋转

(pri,key);

左边小右边大 key

pri 符合堆实现log 的操作

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 #include
                 
                  using namespace std;#define ll long long#define MAXN 100010#define inf 2000000007struct node{ struct node *ch[2]; int key,sz,pri;};typedef struct node *tree;node base[MAXN],nil;tree top,root,null;void Init() //初始化{ top=base; root=null=&nil; null->ch[0]=null->ch[1]=null; null->key=null->pri=2147483647; null->sz=0;}inline int random()//随机{ static int seed=703; return seed=int(seed*48271ll%2147483647);}inline tree newnode(int k)//产生新的点{ top->key=k; top->sz=1; top->pri=random(); top->ch[0]=top->ch[1]=null; return top++;}void Rotate(tree &x,bool d) //旋转{ tree y=x->ch[!d]; x->ch[!d]=y->ch[d]; y->ch[d]=x; x->sz=x->ch[0]->sz+1+x->ch[1]->sz; y->sz=y->ch[0]->sz+1+y->ch[1]->sz; x=y;}void Insert(tree &t,int key) //插入{ if(t==null) t=newnode(key); else { bool d=key>t->key; Insert(t->ch[d],key); //先到叶子再旋转 (t->sz)++; if(t->pri
                  
                   ch[d]->pri) Rotate(t,!d); }}void Delete(tree &t,int key)//删除{ if(t->key!=key) { Delete(t->ch[key>t->key],key); (t->sz)--; } else if(t->ch[0]==null) t=t->ch[1]; else if(t->ch[1]==null) t=t->ch[0]; else { bool d=t->ch[0]->pri
                   
                    ch[1]->pri; Rotate(t,d); Delete(t->ch[d],key); }}tree select(int k){ tree t=root; int tmp; for(;;) { tmp=t->ch[0]->sz+1; if(k==tmp) .//这个点 return t; else if(k>tmp)//右孩子 { k-=tmp; t=t->ch[1]; } else//左边 t=t->ch[0]; }}int main(){ Init(); Insert(root,1); printf("1\n"); Insert(root,2); Insert(root,3); Insert(root,-1); Delete(root,2); printf("%d\n",select(2)->key); return 0;}