Randomized Binary Search Tree

Randomized Binary Search Tree1.cpp

#ifndef RANDOMIZED_BINARY_SEARCH_TREE
#define RANDOMIZED_BINARY_SEARCH_TREE
template<typename T>
class random_bst{
	private:
		struct node{
			T data;
			unsigned size;
			node *ch[2];
			node(const T &d):data(d),size(1){ch[0]=ch[1]=0;}
			inline void up(){
				size=(ch[0]?ch[0]->size:0)+(ch[1]?ch[1]->size:0)+1;
			}
		}*root;
		unsigned seed;
		inline int size(node *o){return o?o->size:0;}
		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->up();
		}
		inline int ran(){
			return seed=0xdefaced*seed+1;
		}
		void clear(node *&p){
			if(p)clear(p->ch[0]),clear(p->ch[1]),delete p;
		}
		void insert_as_root(node *&p,const T &data){
			if(!p)p=new node(data);
			else{
				p->size++;
				insert_as_root(p->ch[p->data<data],data);
				rotate(p,!(p->data<data));
			}
		}
		void insert(node *&p,const T &data){
			if(ran()%(size(p)+1)==0){
				insert_as_root(p,data);
			}else{
				p->size++;
				insert(p->ch[p->data<data],data);
			}
		}
		node *merge(node *a,node *b){
			if(!a||!b)return a?a:b;
			if(ran()%(a->size+b->size)<a->size){
				a->ch[1]=merge(a->ch[1],b);
				a->up();
				return a;
			}else{
				b->ch[0]=merge(a,b->ch[0]);
				b->up();
				return b;
			}
		}
		bool erase(node *&o,const T &data){
			if(!o)return 0;
			if(o->data==data){
				node *t=o;
				o=merge(o->ch[0],o->ch[1]);
				delete t;
				return 1;
			}else if(erase(o->ch[o->data<data],data)){
				o->size--;return 1;
			}return 0;
		}
	public:
		random_bst(unsigned x=20150112):root(0),seed(x){}
		~random_bst(){clear(root);}
		inline void clear(){clear(root),root=0;}
		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;)
			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;)
			if(o->data<data)cnt+=size(o->ch[0])+1,o=o->ch[1];
			else o=o->ch[0];
			return cnt;
		}
		inline const T&kth(int k){
			for(node *o=root;;)
			if(k<=size(o->ch[0]))o=o->ch[0];
			else if(k==size(o->ch[0])+1)return o->data;
			else k-=size(o->ch[0])+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)
			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)
			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 size(root);}
};
#endif

Randomized Binary Search Tree2.cpp

#ifndef RANDOMIZED_BINARY_SEARCH_TREE
#define RANDOMIZED_BINARY_SEARCH_TREE
template<typename T>
class random_bst{
	private:
		struct node{
			T data;
			unsigned 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_as_root(node *&p,const T &data){
			if(!p->s){
				p=new node(data);
				p->ch[0]=p->ch[1]=nil;
			}else{
				++p->s;
				insert_as_root(p->ch[p->data<data],data);
				rotate(p,!(p->data<data));
			}
		}
		void insert(node *&p,const T &data){
			if(ran()%(p->s+1)==0){
				insert_as_root(p,data);
			}else{
				++p->s;
				insert(p->ch[p->data<data],data);
			}
		}
		bool erase(node *&o,const T &data){
			if(!o->s)return 0;
			if(o->data==data){
				if(!o->ch[0]->s||!o->ch[1]->s){
					node *t=o;
					o=o->ch[0]->s?o->ch[0]:o->ch[1];
					delete t;
				}else{
					--o->s;
					bool d=ran()%(o->ch[0]->s+o->ch[1]->s)<o->ch[0]->s;
					rotate(o,d);
					erase(o->ch[d],data);
				}
				return 1;
			}else 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:
		random_bst(unsigned s=20150112):nil(new node),root(nil),x(s){}
		~random_bst(){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