Treap是一种自平衡二叉搜索树,Treap=Tree+Heap.
在一棵二叉搜索树中插入元素的时候,位置是惟一的,但是由于插入的顺序不同,树的形状会不同.在树上进行操作的复杂度取决于树的深度,所以树越矮胖越好,我们称能保持矮胖身材的树为平衡树.最理想的是完全二叉树,此时的复杂度为O(logn),但是由于无法控制插入元素的顺序,所以无法准确地控制树的形状.但是随机顺序插入的树基本上是平衡树.Treap利用的就是类似的原理.给每一个点带一个优先级(rank),类比Heap,保证优先级小(或大)的点在上面,这样插入元素时,新元素的优先级不同,Heap的调整方式就不同,最终树的形态就不同.那么在每次插入时都随机一个优先级,这样相当于每次都随机改变树的形状,以达到和随机插入元素相同的效果.这样的Treap可以称作自平衡二叉树,每次操作的复杂度约为O(logn).
下面是代码实现:
1.rotate函数是用LRJ书上的形式,其中o点表示的是当前子树的根节点,所以需要引用.每次旋转之后相当于改变了新建了一个新的根节点,并将新的子树连好,来替代原先的根节点.这样的操作对子树上面的点是没有影响的,所以插入可以写成递归的形式.但这样的旋转操作的对象是某个子树的根节点,处理的时一个子树,而不是具体的一个点,所以不方便对一个具体的点进行连续的旋转操作,而插入结束后还要判断优先级,可能会将某一个点连旋转多次,用非递归的写法就难以实现了.
2.remove函数有两种算法:
(1).如果当前节点只有一个或没有子树,就直接删除当前点,并用惟一的子树(或null)替换当前点即可.如果当前点两个子树都存在,把优先级小(或大)的子节点转上去,再在另一个子树中递归删除当前点.
(2).如果当前点没有子树,直接删除,否则就将优先级小的子节点转到上面,再在另一棵子树中递归删除当前点.
我一般用第一种.
3.rank,kth,pre,suc函数都可以写成递归或非递归的版本.
递归:
1 #include <cstdio> 2 #include <cstdlib> 3 #include <algorithm> 4 using namespace std; 5 6 const int oo=~0u>>1; 7 8 struct Treap{ 9 struct node{ 10 node* ch[2]; 11 int v,s,r,c; 12 node(int v,node* t):v(v){ ch[0]=ch[1]=t; r=rand(); s=c=1; } 13 void push_up(){ s=ch[0]->s+ch[1]->s+c; } 14 }*root,*null; 15 Treap(){ 16 null=new node(0,NULL); 17 null->s=null->c=0; 18 null->r=oo; 19 root=null; 20 } 21 void rotate(node* &o,bool d){ 22 node* k=o->ch[!d]; o->ch[!d]=k->ch[d]; k->ch[d]=o; 23 o->push_up(); k->push_up(); o=k; 24 } 25 void insert(node* &o,int x){ 26 if(o==null) o=new node(x,null); 27 else{ 28 if(o->v==x) o->c++,o->s++; 29 else{ 30 bool d=x>o->v; 31 insert(o->ch[d],x); 32 if(o->ch[d]<o) rotate(o,!d); 33 o->push_up(); 34 } 35 } 36 } 37 void remove(node* &o,int x){ 38 if(o->v==x){ 39 if(o->c>1){ 40 o->c--; 41 o->push_up(); 42 } 43 else{ 44 if(o->ch[0]!=null&&o->ch[1]!=null){ 45 bool d=o->ch[0]->r<o->ch[1]->r; 46 rotate(o,d); remove(o->ch[d],x); 47 o->push_up(); 48 } 49 else{ 50 node* u=o; 51 if(o->ch[0]==null) o=o->ch[1]; 52 else o=o->ch[0]; 53 delete u; 54 } 55 } 56 } 57 else{ 58 bool d=x>o->v; 59 remove(o->ch[d],x); 60 } 61 } 62 int kth(node* o,int k){ 63 int s=o->ch[0]->s+o->c; 64 if(k>o->ch[0]->s&&k<=s) return o->v; 65 if(k<=o->ch[0]->s) return kth(o->ch[0],k); 66 else return kth(o->ch[1],k-s); 67 } 68 int rank(node* o,int x){ 69 int s=o->ch[0]->s+o->v; 70 if(x==o->v) return o->ch[0]->s+1; 71 if(x<o->v) return rank(o->ch[0],x); 72 else return s+rank(o->ch[1],x); 73 } 74 int pre(node* o,int x){ 75 if(o==null) return -oo; 76 if(o->v<x) return max(o->v,pre(o->ch[1],x)); 77 else return pre(o->ch[0],x); 78 } 79 int suc(node* o,int x){ 80 if(o==null) return oo; 81 if(o->v>x) return min(o->v,suc(o->ch[0],x)); 82 else return suc(o->ch[1],x); 83 } 84 }tree; 85 86 int main(){ 87 return 0; 88 }
非递归:
1 #include <cstdio> 2 #include <cstdlib> 3 #include <algorithm> 4 using namespace std; 5 6 const int oo=~0u>>1; 7 8 struct Treap{ 9 struct node{ 10 node* ch[2]; 11 int v,s,r,c; 12 node(int v,node* t):v(v){ ch[0]=ch[1]=t; r=rand(); s=c=1; } 13 void push_up(){ s=ch[0]->s+ch[1]->s+c; } 14 }*root,*null; 15 Treap(){ 16 null=new node(0,NULL); 17 null->s=null->c=0; 18 null->r=oo; 19 root=null; 20 } 21 void rotate(node* &o,bool d){ 22 node* k=o->ch[!d]; o->ch[!d]=k->ch[d]; k->ch[d]=o; 23 o->push_up(); k->push_up(); o=k; 24 } 25 void insert(node* &o,int x){ 26 if(o==null) o=new node(x,null); 27 else{ 28 if(o->v==x) o->c++,o->s++; 29 else{ 30 bool d=x>o->v; 31 insert(o->ch[d],x); 32 if(o->ch[d]<o) rotate(o,!d); 33 o->push_up(); 34 } 35 } 36 } 37 void remove(node* &o,int x){ 38 if(o->v==x){ 39 if(o->c>1){ 40 o->c--; 41 o->push_up(); 42 } 43 else{ 44 if(o->ch[0]!=null&&o->ch[1]!=null){ 45 bool d=o->ch[0]->r<o->ch[1]->r; 46 rotate(o,d); remove(o->ch[d],x); 47 o->push_up(); 48 } 49 else{ 50 node* u=o; 51 if(o->ch[0]==null) o=o->ch[1]; 52 else o=o->ch[0]; 53 delete u; 54 } 55 } 56 } 57 else{ 58 bool d=x>o->v; 59 remove(o->ch[d],x); 60 } 61 } 62 int kth(int k){ 63 for(node* t=root;t!=null;){ 64 int s=t->ch[0]->s+t->c; 65 if(k>t->ch[0]->s&&k<=s) return t->v; 66 else if(k>s) t=t->ch[1], k-=s; 67 else t=t->ch[0]; 68 } 69 } 70 int rank(int x){ 71 int ret=0; 72 for(node* t=root;t!=null;){ 73 int s=t->ch[0]->s+t->c; 74 if(x>t->v) ret+=s, t=t->ch[1]; 75 else t=t->ch[0]; 76 } 77 return ret; 78 } 79 int pre(int x){ 80 int ret=-oo; 81 for(node*t=root;t!=null;){ 82 if(t->v<x) ret=t->v, t=t->ch[1]; 83 else t=t->ch[0]; 84 } 85 return ret; 86 } 87 int suc(int x){ 88 int ret=oo; 89 for(node* t=root;t!=null;){ 90 if(t->v>x) ret=t->v, t=t->ch[0]; 91 else t=t->ch[1]; 92 } 93 return ret; 94 } 95 }tree; 96 97 int main(){ 98 return 0; 99 }