[ Randomized Binary Search Tree ] 隨機二分查找樹

今天來介紹隨機二分查找樹，因為看了很多外國的文章看了半天都看不懂，現在好不容易看懂英文了，就把它用中文的方式來介紹吧!
隨機二分查找樹，是利用隨機數或機率分布來達到平衡的條件，其證明以附在連結中。
利用隨機數的方法包括Treap，但是這太常見了，所以掠過。

這邊要介紹不需額外再節點紀錄隨機值的方式，透過其節點大小來計算其是否為根或是根據節點大小的比例隨機插入。

維持平衡用左旋根右旋(參見:樹旋轉):
接下來來講解一下它的插入
這裡會用到兩個函數:
insert():插入節點
insert_as_root(node *&p,T k):將k插入子樹p並做為p的根節點
為甚麼要這樣做呢?
當在對節點p進行插入時，新插入點根據隨機分布會有1/(size(p)+1)的機率成為這顆子樹的根
因此可以以遞迴處理
若此節點的值>插入值，則插入其左節點，然後右旋，反之亦然
其常數很小，所以常常插入時間比size balanced tree快，但是深度太大，刪除時間較慢
其平均深度等價於在一棵普通的BST進行隨機插入最終的平均深度，因此為2nlogn

而對於刪除節點，和Treap一樣，有兩種不同的做法:

第一種是透過與左偏樹類似的方法刪除，不需要旋轉，通常效率交高
合併左右子樹，然後刪除其根節點
合併的方式利用了隨機分布的概念
假設需將a,b合併
則有size(a)/(size(a)+size(b))的機率將b合併到a子樹
反之有size(b)/(size(a)+size(b))的機率將a合併到b子樹

第二種作法完全依賴於旋轉
在刪除時如果要被刪除的節點不是一條鏈的話，就按造隨機的概念進行旋轉
有size(左子樹)/(size(左子樹)+size(右子樹))的機率進行右旋
反之有size(右子樹)/(size(左子樹)+size(右子樹))的機率進行左旋

以下為第一種作法(效率較高):

	#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

view raw Randomized Binary Search Tree1.cpp hosted with ❤ by GitHub

以下為第二種作法:

	#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

view raw Randomized Binary Search Tree2.cpp hosted with ❤ by GitHub