Treap 模板

這是 旋轉式Treap 的模板，是目前所有平衡樹中code最為簡便的一種。
插入和刪除的時間複雜度跟Randomized binary search tree一樣，是在演算法競賽中最適合使用的平衡樹。
因為 分裂/合併式 Treap 可以完全被 分裂/合併式 Randomized binary search tree取代，故不提供

做法1，完全依靠旋轉進行平衡(刪除速度較慢):

	#ifndef TREAP
	#define TREAP
	template<typename T>
	class treap{
	private:
	struct node{
	T data;
	unsigned fix;
	int size;
	node *ch[2];
	node(const T&d):data(d),size(1){}
	node():size(0){ch[0]=ch[1]=this;}
	}*nil,*root;
	unsigned x;
	inline unsigned ran(){
	return x=x*0xdefaced+1;
	}
	inline void rotate(node *&a,bool d){
	node *b=a;
	a=a->ch[!d];
	a->size=b->size;
	b->ch[!d]=a->ch[d];
	a->ch[d]=b;
	b->size=b->ch[0]->size+b->ch[1]->size+1;
	}
	void insert(node *&o,const T &data){
	if(!o->size){
	o=new node(data),o->fix=ran();
	o->ch[0]=o->ch[1]=nil;
	}else{
	o->size++;
	bool d=o->data<data;
	insert(o->ch[d],data);
	if(o->ch[d]->fix>o->fix)rotate(o,!d);
	}
	}
	bool success_erase(node *&o){
	if(!o->ch[0]->size||!o->ch[1]->size){
	node *t=o;
	o=o->ch[0]->size?o->ch[0]:o->ch[1];
	delete t;
	}else{
	o->size--;
	bool d=o->ch[0]->fix>o->ch[1]->fix;
	rotate(o,d);
	success_erase(o->ch[d]);
	}
	return 1;
	}
	bool erase(node *&o,const T &data){
	if(!o->size)return 0;
	if(o->data==data)return success_erase(o);
	if(erase(o->ch[o->data<data],data)){
	o->size--;return 1;
	}else return 0;
	}
	void clear(node *&o){
	if(o->size)clear(o->ch[0]),clear(o->ch[1]),delete o;
	}
	public:
	treap(unsigned s=20150119):nil(new node),root(nil),x(s){}
	~treap(){clear(root),delete nil;}
	inline void clear(){clear(root),root=nil;}
	inline void insert(const T &data){
	insert(root,data);
	}
	inline bool erase(const T &data){
	return erase(root,data);
	}
	inline bool find(const T&data){
	for(node *o=root;o->size;)
	if(o->data==data)return 1;
	else o=o->ch[o->data<data];
	return 0;
	}
	inline int rank(const T&data){
	int cnt=0;
	for(node *o=root;o->size;)
	if(o->data<data)cnt+=o->ch[0]->size+1,o=o->ch[1];
	else o=o->ch[0];
	return cnt;
	}
	inline const T&kth(int k){
	for(node *o=root;;)
	if(k<=o->ch[0]->size)o=o->ch[0];
	else if(k==o->ch[0]->size+1)return o->data;
	else k-=o->ch[0]->size+1,o=o->ch[1];
	}
	inline const T&operator[](int k){
	return kth(k);
	}
	inline const T&preorder(const T&data){
	node *x=root,*y=0;
	while(x->size)
	if(x->data<data)y=x,x=x->ch[1];
	else x=x->ch[0];
	if(y)return y->data;
	return data;
	}
	inline const T&successor(const T&data){
	node *x=root,*y=0;
	while(x->size)
	if(data<x->data)y=x,x=x->ch[0];
	else x=x->ch[1];
	if(y)return y->data;
	return data;
	}
	inline int size(){return root->size;}
	};
	#endif

view raw treap1.cpp hosted with ❤ by GitHub

作法2，刪除時合併左右子樹(刪除速度較快):

	#ifndef TREAP
	#define TREAP
	template<typename T>
	class treap{
	private:
	struct node{
	T data;
	unsigned fix;
	int s;
	node *ch[2];
	node(const T&d):data(d),s(1){}
	node():s(0){ch[0]=ch[1]=this;}
	}*nil,*root;
	unsigned x;
	inline unsigned ran(){
	return x=x*0xdefaced+1;
	}
	inline void rotate(node *&a,bool d){
	node *b=a;
	a=a->ch[!d];
	a->s=b->s;
	b->ch[!d]=a->ch[d];
	a->ch[d]=b;
	b->s=b->ch[0]->s+b->ch[1]->s+1;
	}
	void insert(node *&o,const T &data){
	if(!o->s){
	o=new node(data),o->fix=ran();
	o->ch[0]=o->ch[1]=nil;
	}else{
	o->s++;
	bool d=o->data<data;
	insert(o->ch[d],data);
	if(o->ch[d]->fix>o->fix)rotate(o,!d);
	}
	}
	node *merge(node *a,node *b){
	if(!a->s||!b->s)return a->s?a:b;
	if(a->fix>b->fix){
	a->ch[1]=merge(a->ch[1],b);
	a->s=a->ch[0]->s+a->ch[1]->s+1;
	return a;
	}else{
	b->ch[0]=merge(a,b->ch[0]);
	b->s=b->ch[0]->s+b->ch[1]->s+1;
	return b;
	}
	}
	bool erase(node *&o,const T &data){
	if(!o->s)return 0;
	if(o->data==data){
	node *t=o;
	o=merge(o->ch[0],o->ch[1]);
	delete t;
	return 1;
	}
	if(erase(o->ch[o->data<data],data)){
	o->s--;return 1;
	}else return 0;
	}
	void clear(node *&o){
	if(o->s)clear(o->ch[0]),clear(o->ch[1]),delete o;
	}
	public:
	treap(unsigned s=20150119):nil(new node),root(nil),x(s){}
	~treap(){clear(root),delete nil;}
	inline void clear(){clear(root),root=nil;}
	inline void insert(const T &data){
	insert(root,data);
	}
	inline bool erase(const T &data){
	return erase(root,data);
	}
	inline bool find(const T&data){
	for(node *o=root;o->s;)
	if(o->data==data)return 1;
	else o=o->ch[o->data<data];
	return 0;
	}
	inline int rank(const T&data){
	int cnt=0;
	for(node *o=root;o->s;)
	if(o->data<data)cnt+=o->ch[0]->s+1,o=o->ch[1];
	else o=o->ch[0];
	return cnt;
	}
	inline const T&kth(int k){
	for(node *o=root;;)
	if(k<=o->ch[0]->s)o=o->ch[0];
	else if(k==o->ch[0]->s+1)return o->data;
	else k-=o->ch[0]->s+1,o=o->ch[1];
	}
	inline const T&operator[](int k){
	return kth(k);
	}
	inline const T&preorder(const T&data){
	node *x=root,*y=0;
	while(x->s)
	if(x->data<data)y=x,x=x->ch[1];
	else x=x->ch[0];
	if(y)return y->data;
	return data;
	}
	inline const T&successor(const T&data){
	node *x=root,*y=0;
	while(x->s)
	if(data<x->data)y=x,x=x->ch[0];
	else x=x->ch[1];
	if(y)return y->data;
	return data;
	}
	inline int size(){return root->s;}
	};
	#endif

view raw treap2.cpp hosted with ❤ by GitHub