[ basic operation of naive order statistic tree ] 樸素二元搜尋樹 名次樹的基本操作

一般的名次樹支援以下幾種操作:

1.插入
2.刪除
3.查找
4.求節點大小
5.求元素名次
6.求第k大
7.求前驅
8.求後繼

之前寫的模板已經有了前六種操作，因此我會在本模板中附上求前驅跟後繼的操作
前驅與後繼並不是名次樹才有的操作，在不記錄節點大小的情形下也能求得
關於求前驅跟後繼操作的說明可以參考 随机平衡二叉查找树Treap的分析与应用 這篇文章

以下提供模板:

	#ifndef NAIVE_BINARY_SEARCH_TREE
	#define NAIVE_BINARY_SEARCH_TREE
	template<typename T>
	class bs_tree{
	private:
	struct node{
	node *ch[2];
	int s;
	T data;
	node(const T&d):s(1),data(d){ch[0]=ch[1]=0;}
	}*root;
	inline int size(node *o){return o?o->s:0;}
	void insert(node *&o,const T&data){
	if(!o)o=new node(data);
	else o->s++,insert(o->ch[o->data<data],data);
	}
	inline void success_erase(node *&o){
	node *t=o;
	o=o->ch[0]?o->ch[0]:o->ch[1];
	delete t;
	}
	bool erase(node *&o,const T &data){
	if(!o)return 0;
	if(o->data==data){
	if(!o->ch[0]||!o->ch[1])success_erase(o);
	else{
	o->s--;
	node **t=&o->ch[1];
	for(;(*t)->ch[0];t=&(*t)->ch[0])(*t)->s--;
	o->data=(*t)->data;
	success_erase(*t);
	}return 1;
	}else if(erase(o->ch[o->data<data],data)){
	o->s--;return 1;
	}return 0;
	}
	node *preorder(node *&x,node *y,const T&data){
	if(!x)return y;
	if(x->data<data)return preorder(x->ch[1],x,data);
	else return preorder(x->ch[0],y,data);
	}
	node *successor(node *&x,node *y,const T&data){
	if(!x)return y;
	if(data<x->data)return successor(x->ch[0],x,data);
	else return successor(x->ch[1],y,data);
	}
	void clear(node *&p){
	if(p)clear(p->ch[0]),clear(p->ch[1]),delete p;
	}
	public:
	bs_tree():root(0){}
	~bs_tree(){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 const T&preorder(const T&data){
	node *o=preorder(root,0,data);
	if(o)return o->data;
	return data;
	}
	inline const T&successor(const T&data){
	node *o=successor(root,0,data);
	if(o)return o->data;
	return data;
	}
	inline int size(){return size(root);}
	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);
	}
	};
	#endif

view raw bst.cpp hosted with ❤ by GitHub

[ AA tree ] AA樹

AA樹是紅黑樹的一種變種，是Arne Andersson教授在1993年年在他的論文"Balanced search trees made simple"中介紹，設計的目的是減少紅黑樹考慮的不同情況。區別於紅黑樹的是，AA樹的紅結點只能作為右葉子。另外AA樹為實現方便，不再使用紅黑兩種顏色，而是用level標記結點，結點中的level相當於紅黑樹中結點的黑高度。

其主要透過skew和split兩種旋轉來進行平衡的，插入時只能為紅節點，故會出現不符合其規定則進行平衡操作

若想進一步了解其平衡操作請參考維基百科
在實作中，skew為右璇，split為左旋。本模板以rotate(o,0)、rotate(o,1)代表

以下提供模板:

	#ifndef ARNE_ANDERSSON_TREE
	#define ARNE_ANDERSSON_TREE
	template<typename T>
	class aa_tree{
	private:
	struct node{
	node *ch[2];
	int s,level;
	T data;
	node(const T&d):s(1),level(1),data(d){}
	node():s(0),level(0){ch[0]=ch[1]=this;}
	}*nil,*root;
	inline void rotate(node *&a,bool d){
	if(a->level==a->ch[d]->ch[d]->level){
	node *b=a;
	a=a->ch[d];
	b->ch[d]=a->ch[!d];
	a->ch[!d]=b;
	if(d)a->level++;
	a->s=b->s;
	b->s=b->ch[0]->s+b->ch[1]->s+1;
	}
	}
	inline void erase_fix(node *&o){
	if(o ->ch[0]->level<o->level-1||o->ch[1]->level<o->level-1){
	if(o->ch[1]->level>--o->level)o->ch[1]->level=o->level;
	rotate(o,0);
	if(o->ch[1]->s)rotate(o->ch[1],0);
	if(o->ch[1]->ch[1]->s)rotate(o->ch[1]->ch[1],0);
	rotate(o,1);
	if(o->ch[1]->s)rotate(o->ch[1],1);
	}
	}
	void insert(node *&o,const T&data){
	if(!o->s){
	o=new node(data);
	o->ch[0]=o->ch[1]=nil;
	}else{
	o->s++;
	insert(o->ch[o->data<data],data);
	rotate(o,0);
	rotate(o,1);
	}
	}
	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--;
	node *t=o->ch[1];
	while(t->ch[0]->s)t=t->ch[0];
	o->data=t->data;
	erase(o->ch[1],t->data);
	erase_fix(o);
	}return 1;
	}else if(erase(o->ch[o->data<data],data)){
	o->s--,erase_fix(o);
	return 1;
	}else return 0;
	}
	void clear(node *&o){
	if(o->s)clear(o->ch[0]),clear(o->ch[1]),delete(o);
	}
	public:
	aa_tree():nil(new node){
	root=nil->ch[0]=nil->ch[1]=nil;
	}
	~aa_tree(){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){
	node *o=root;
	while(o->s&&o->data!=data)o=o->ch[o->data<data];
	return o->s?1: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 aa_tree.cpp hosted with ❤ by GitHub

[ symmetric binary B-tree ( red black tree ) ] 對稱二叉B樹 ( 紅黑樹 )

紅黑樹是一種有最壞情況擔保的平衡樹，其插入最多會用到2個旋轉，刪除最多用到3個旋轉，其犧牲些許的平衡來加快插入刪除的速度，並有高度上h<=2*log(n+1)的保證。
故其插入刪除之常數會比較小，而查詢之常數會較大(相對於一般高度平衡樹)，而一般的函式庫裡的"關聯數組"通常適用紅黑樹實做的
其平衡原因及方法請參考維基百科
因其操作複雜故不常在競賽中被使用，且刪除速度較size balanced tree慢約2倍

以下提供模板:

	/* 0 => black , 1 => red */
	#ifndef SYMMETRIC_BINARY_B_TREE
	#define SYMMETRIC_BINARY_B_TREE
	template<typename T>
	class rb_tree{
	private:
	struct node{
	node *ch[2],*pa;
	int s;
	bool c;
	T data;
	node(const T&d,node*p):pa(p),s(1),c(1),data(d){}
	node():s(0),c(0){ch[0]=ch[1]=pa=this;}
	}*nil,*root;
	inline void rotate(node*o,bool d){
	if(!o->pa->s)root=o->ch[!d];
	else o->pa->ch[o==o->pa->ch[1]]=o->ch[!d];
	o->ch[!d]->pa=o->pa;
	o->pa=o->ch[!d];
	o->ch[!d]=o->pa->ch[d];
	o->pa->ch[d]=o;
	if(o->ch[!d]->s)o->ch[!d]->pa=o;
	o->pa->s=o->s;
	o->s=o->ch[0]->s+o->ch[1]->s+1;
	}
	inline node *find(node*o,const T&data){
	while(o->s&&o->data!=data)o=o->ch[o->data<data];
	return o->s?o:0;
	}
	inline void insert_fix(node*&o){
	while(o->pa->c){
	bool d=o->pa==o->pa->pa->ch[0];
	node *uncle=o->pa->pa->ch[d];
	if(uncle->c){
	uncle->c=o->pa->c=0;
	o->pa->pa->c=1;
	o=o->pa->pa;
	}else{
	if(o==o->pa->ch[d]){
	o=o->pa;
	rotate(o,!d);
	}
	o->pa->c=0;
	o->pa->pa->c=1;
	rotate(o->pa->pa,d);
	}
	}
	root->c=0;
	}
	inline void erase_fix(node*&x){
	while(x!=root&&!x->c){
	bool d=x==x->pa->ch[0];
	node *w=x->pa->ch[d];
	if(w->c){
	w->c=0;
	x->pa->c=1;
	rotate(x->pa,!d);
	w=x->pa->ch[d];
	}
	if(!w->ch[0]->c&&!w->ch[1]->c){
	w->c=1,x=x->pa;
	}else{
	if(!w->ch[d]->c){
	w->ch[!d]->c=0;
	w->c=1;
	rotate(w,d);
	w=x->pa->ch[d];
	}
	w->c=x->pa->c;
	w->ch[d]->c=x->pa->c=0;
	rotate(x->pa,!d);
	break;
	}
	}
	x->c=0;
	}
	void clear(node*&o){
	if(o->s)clear(o->ch[0]),clear(o->ch[1]),delete(o);
	}
	public:
	rb_tree():nil(new node),root(nil){}
	~rb_tree(){clear(root),delete nil;}
	inline void clear(){clear(root),root=nil;}
	inline void insert(const T&data){
	node *o=root;
	if(!o->s){
	root=new node(data,nil);
	root->ch[0]=root->ch[1]=nil;
	}else{
	for(;;){
	o->s++;
	bool d=o->data<data;
	if(o->ch[d]->s)o=o->ch[d];
	else{
	o->ch[d]=new node(data,o),o=o->ch[d];
	o->ch[0]=o->ch[1]=nil;
	break;
	}
	}
	}
	insert_fix(o);
	}
	inline bool erase(const T&data){
	node *o=find(root,data);
	if(!o)return 0;
	node *t=o,*p;
	if(o->ch[0]->s&&o->ch[1]->s){
	t=o->ch[1];
	while(t->ch[0]->s)t=t->ch[0];
	}
	p=t->ch[!t->ch[0]->s];
	p->pa=t->pa;
	if(!t->pa->s)root=p;
	else t->pa->ch[t->pa->ch[1]==t]=p;
	if(t!=o)o->data=t->data;
	for(o=t->pa;o->s;o=o->pa)o->s--;
	if(!t->c)erase_fix(p);
	delete t;
	return 1;
	}
	inline bool find(const T&data){
	return find(root,data);
	}
	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 red black tree.cpp hosted with ❤ by GitHub