4
24
2015
0

【存档】Treap

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...

Category: 数据结构 | Tags: | Read Count: 776

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com