treap（tree+heap）平衡树；
结点定义如下：
struct Node{
Node *ch[2];//左右子树
int r,v;//优先级&值
int cmp(int x)const{if(x==v)return -1;return x>v;}
};
解释一下，treap同时拥有值与优先级，即同时满足heap与BST性质，优先级是一个rand值
接下来就是旋转，旋转代码如下：
//d=0表示左旋，=1表示右旋
void rotate(Node *o,int d){
Node *k=o->ch[d^1];o->ch[d^1]=k->ch[d],k->ch[d]=o,o=k;
}
旋转是很简单的=_-，如果不清楚旋转方法，就找一张图对着代码手动模拟一下吧：）
treap支持插入，删除；
插入代码如下：
void insert(Node *&o,int x){
if(o==null){
o=new Node();
o->ch[0]=o->ch[0]=null;
o->v=x,o->r=rand();
}else{
int d=o->cmp(x);
insert(o->ch[d],x);
if(o->ch[d]->r>o->r)rotate(o,d^1);
}
}
删除代码如下：
void del(Node *&o,int x){
int d=o->cmp(x);
if(d==-1){
if(o->ch[0]==null)o=o->ch[1];
else if(o->ch[1]==null)o=o->ch[0];
else{
int d2=o->ch[0]->r>o->ch[1]->r?1:0;
rotate(o,d2),del(o->ch[d2],x);
}
}else del(o->ch[d],x);
}
loading...
评论 (0)
