[ scapegoat tree ] 替罪羊樹

替罪羊樹論文其中一個作者，Ronald Linn Rivest，同時也是RSA加密算法的R
替罪羊樹是一種不需要旋轉的平衡樹，它會要求使用者給定一個$\alpha$值，其值介於0.5到1之間，$\alpha$越大，插入就越快，查詢就越慢，實驗發現$\alpha$介於0.55~0.75是最佳的，但是具體的值要看使用者的要求
其平衡滿足:
1.
    $\alpha*size(o) \le size(o \to left)$
    $\alpha*size(o) \le size(o \to right)$
2.
    $deep(o) \le log_{1/\alpha} (size(tree))$
當插入節點導致條件2.不滿足時，會往上回溯到第一個不滿足的節點，然後重建這顆節點的子樹成為完美平衡的二元樹
刪除可以用一般的BST刪除法，當不滿足條件時往上回溯到最先不滿足的節點，重建子樹，也可以懶惰刪除，先設立一個標記， 要刪除這個節點就把它做記號，當$\alpha$*全部的節點數量>實際上存在的節點數量，就重建這顆子樹
本文提供一般刪除的方法

其實替罪羊樹的節點是不需要記錄其size的，因為若需要重建，求得size的時間複雜度與重建的時間複雜度相等，這裡為了支援其它有如rank等操作才將size域附加在節點中

插入刪除的均攤時間複雜度為$\ord{logN}$，相較之下朝鮮樹只是他的劣質仿冒品，其複雜度證明請參考此論文

以下為模板:

	#ifndef SCAPEGOAT_TREE
	#define SCAPEGOAT_TREE
	#include<cmath>
	#include<algorithm>
	template<typename T>
	class scapegoat_tree{
	private:
	struct node{
	node *ch[2];
	int s;
	T data;
	node(const T&d):s(1),data(d){}
	node():s(0){ch[0]=ch[1]=this;}
	}*nil,*root,t;
	const double alpha,loga;
	int maxn;
	inline bool isbad(node*o){
	return o->ch[0]->s>alpha*o->s||o->ch[1]->s>alpha*o->s;
	}
	node *flatten(node *x,node *y){
	if(!x->s)return y;
	x->ch[1]=flatten(x->ch[1],y);
	return flatten(x->ch[0],x);
	}
	node *build(node *x,int n){
	if(!n){
	x->ch[0]=nil;
	return x;
	}
	node *y=build(x,n/2);
	node *z=build(y->ch[1],n-1-n/2);
	y->ch[1]=z->ch[0];
	z->ch[0]=y;
	y->s=y->ch[0]->s+y->ch[1]->s+1;
	return z;
	}
	bool insert(node *&o,const T&data,int dp){
	if(!o->s){
	o=new node(data);
	o->ch[0]=o->ch[1]=nil;
	return dp<=0;
	}
	++o->s;
	if(insert(o->ch[o->data<data],data,--dp)){
	if(!isbad(o))return 1;
	o=build(flatten(o,&t),o->s)->ch[0];
	}return 0;
	}
	inline void success_erase(node *&o){
	node *t=o;
	o=o->ch[0]->s?o->ch[0]:o->ch[1];
	delete t;
	}
	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)success_erase(o);
	else{
	--o->s;
	node **t=&o->ch[1];
	for(;(*t)->ch[0]->s;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;
	}else return 0;
	}
	void clear(node *&p){
	if(p->s)clear(p->ch[0]),clear(p->ch[1]),delete p;
	}
	public:
	scapegoat_tree(const double&d=0.75):nil(new node),root(nil),alpha(d),loga(log2(1.0/d)),maxn(1){}
	~scapegoat_tree(){clear(root),delete nil;}
	inline void clear(){clear(root),root=nil;maxn=1;}
	inline void insert(const T&data){
	insert(root,data,std::__lg(maxn)/loga);
	if(root->s>maxn)maxn=root->s;
	}
	inline bool erase(const T&data){
	bool d=erase(root,data);
	if(root->s<alpha*maxn)rebuild();
	return d;
	}
	inline bool find(const T&data){
	node *o=root;
	while(o->s&&o->data!=data)o=o->ch[o->data<data];
	return o->s;
	}
	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 void rebuild(){root=build(flatten(root,&t),maxn=root->s)->ch[0];}
	inline int size(){return root->s;}
	};
	#endif

view raw scapegoat tree2.cpp hosted with ❤ by GitHub

這裡也提供不需要記錄節點大小(size)的平衡方式，相對的一些需要用到附加size域的函數將不能被使用，但插入刪除的效率不變

	#ifndef NOSIZE_SCAPEGOAT_TREE
	#define NOSIZE_SCAPEGOAT_TREE
	#include<cmath>
	#include<algorithm>
	template<typename T>
	class scapegoat_tree{
	private:
	struct node{
	node *ch[2];
	T data;
	node(const T&d):data(d){ch[0]=ch[1]=0;}
	node(){}
	}*root,t;
	const double alpha,loga;
	int maxn,n;
	int size(node *o){
	return o?size(o->ch[0])+size(o->ch[1])+1:0;
	}
	node *flatten(node *x,node *y){
	if(!x)return y;
	x->ch[1]=flatten(x->ch[1],y);
	return flatten(x->ch[0],x);
	}
	node *build(node *x,int n){
	if(!n){
	x->ch[0]=0;
	return x;
	}
	node *y=build(x,n/2);
	node *z=build(y->ch[1],n-1-n/2);
	y->ch[1]=z->ch[0];
	z->ch[0]=y;
	return z;
	}
	int insert(node *&o,const T&data,int dp){
	if(!o){
	o=new node(data);
	return dp<=0;
	}
	bool d=o->data<data;
	int ds1=insert(o->ch[d],data,--dp);
	if(ds1){
	int ds2=size(o->ch[!d]),n=ds1+ds2+1;
	if(ds1<=alpha*n&&ds2<=alpha*n)return n;
	o=build(flatten(o,&t),n)->ch[0];
	}return 0;
	}
	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{
	node **t=&o->ch[1];
	for(;(*t)->ch[0];t=&(*t)->ch[0]);
	o->data=(*t)->data;
	success_erase(*t);
	}return 1;
	}else return erase(o->ch[o->data<data],data);
	}
	void clear(node *&p){
	if(p)clear(p->ch[0]),clear(p->ch[1]),delete p;
	}
	public:
	scapegoat_tree(const double&d=0.75):root(0),alpha(d),loga(log2(1.0/d)),maxn(1),n(0){}
	~scapegoat_tree(){clear(root);}
	inline void clear(){clear(root),root=0;maxn=1,n=0;}
	inline void insert(const T&data){
	insert(root,data,std::__lg(maxn)/loga);
	if(++n>maxn)maxn=n;
	}
	inline bool erase(const T&data){
	bool d=erase(root,data);
	if(d&&--n<alpha*maxn)rebuild();
	return d;
	}
	inline bool find(const T&data){
	node *o=root;
	while(o&&o->data!=data)o=o->ch[o->data<data];
	return o;
	}
	inline const T& min(){
	node *o=root;
	while(o->ch[0])o=o->ch[0];
	return o->data;
	}
	inline const T& max(){
	node *o=root;
	while(o->ch[1])o=o->ch[1];
	return o->data;
	}
	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 void rebuild(){root=build(flatten(root,&t),maxn=n)->ch[0];}
	inline int size(){return n;}
	};
	#endif

view raw scapegoat tree1.cpp hosted with ❤ by GitHub

如果編譯發現沒有__lg()這個函數的話，請在程式碼開頭附上這份code:

	namespace std{
	inline int __lg(int n){//Precondition: n >= 0
	int k=0;
	for(;n!=0;n>>=1)++k;
	return k?--k:1;
	}
	}

view raw __lg.cpp hosted with ❤ by GitHub

[ korea tree ] 朝鮮樹

某天albus YY出來了一個沒有旋轉操作的平衡樹，由於albus的真名(华中科技大学附属中学 金正中)聽起來很像朝鮮主席，所以就叫朝鮮樹了！

朝鮮樹是一種不需旋轉的 自平衡二元搜尋樹，利用當深度大於max_deep(通常取sqrt(N))時暴力重建的方式讓平均時間為$\ord{N*sqrt(N)}$，是一種很糟糕的平衡樹，但是我們還是要理解他，因為這樣暴力重建的概念會在其他樹上用到。
若題目的要求數據量<=500000時可以使用

所有操作都與本篇其他樹差不多只多了個rebuild函數，它會暴力將整顆樹重建成深度logN的平衡樹

對於重建的部分則使用了拍扁重建法，將樹先拍扁成鍊表後重建，只需要花費$\ord 1$的空間複雜度

以下提供模板:

	#ifndef KOREA_TREE
	#define KOREA_TREE
	template<typename T>
	class korea_tree{
	private:
	struct node{
	node *ch[2];
	T data;
	int s;
	node(const T&d):data(d),s(1){}
	node():s(0){ch[0]=ch[1]=this;}
	}*nil,*root,t;
	int max_deep,d;
	void insert(node *&o,const T&data){
	if(!o->s){
	o=new node(data);
	o->ch[0]=o->ch[1]=nil;
	}else o->s++,d++,insert(o->ch[o->data<data],data);
	}
	inline void success_erase(node *&o){
	node *t=o;
	o=o->ch[0]->s?o->ch[0]:o->ch[1];
	delete t;
	}
	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)success_erase(o);
	else{
	o->s--;
	node **t=&o->ch[1];
	for(;(*t)->ch[0]->s;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;
	}else return 0;
	}
	node *flatten(node *x,node *y){
	if(!x->s)return y;
	x->ch[1]=flatten(x->ch[1],y);
	return flatten(x->ch[0],x);
	}
	node *build(node *x,int n){
	if(!n){
	x->ch[0]=nil;
	return x;
	}
	node *y=build(x,n/2);
	node *z=build(y->ch[1],n-1-n/2);
	y->ch[1]=z->ch[0];
	z->ch[0]=y;
	y->s=y->ch[0]->s+y->ch[1]->s+1;
	return z;
	}
	void clear(node *&p){
	if(p->s)clear(p->ch[0]),clear(p->ch[1]),delete p;
	}
	public:
	korea_tree(int d=1000):nil(new node),root(nil),max_deep(d){}
	~korea_tree(){clear(root),delete nil;}
	inline void clear(){clear(root),root=nil;}
	inline void insert(const T&data){
	d=0;
	insert(root,data);
	if(d>=max_deep)rebuild();
	}
	inline bool erase(const T&data){
	return erase(root,data);
	}
	inline void rebuild(){
	root=build(flatten(root,&t),root->s)->ch[0];
	}
	inline bool find(const T&data){
	node *o=root;
	while(o->s&&o->data!=data)o=o->ch[o->data<data];
	return o->s;
	}
	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 korea_tree.cpp hosted with ❤ by GitHub

[ Splay Tree ] 伸展樹模板

最近研究了伸展樹，它可以在均攤$\ord{logN}$的時間完成伸展操作，所謂的伸展操作就是將某個節點旋轉(rotate)到根(root)的過程，因為我們大部分在搜尋資料時，常常都只會用到特定的資料，其他大多數的資料是較少被搜尋的，因此將常被搜尋的資料靠近根是很好的策略，伸展樹由此被發明。
因為伸展樹可以分裂合併，所以可以取代分裂合併式treap或是分裂合併式randomize binary tree的功能，可以在競賽中被使用，而普通的伸展樹效率不高，故本文只介紹作區間處理的伸展樹
之後的link-cut tree會用到他，所以必須要能理解
例題: UVA 11922

定義伸展樹節點:(T為資料型態)

	struct node{
	T data;
	node *ch[2];
	int s;
	node(const T&d):data(d), s(1){}
	node():s(0){}
	/*cmp是很重要的一個函式一定要理解*/
	char cmp(int v){
	int d=v-ch[0]->s;
	if(d==1)return -1;
	return d>0;
	}
	void down(){
	/*可以加一些下推懶惰標記*/
	}
	void up(){
	s=ch[0]->s+ch[1]->s+1;
	/*可以加一些上推懶惰標記*/
	}
	}*root,*nil;

view raw splay_tree_node.cpp hosted with ❤ by GitHub

初始化時nil的l,r要指向自己

	nil=new node();
	root=nil->ch[0]=nil->ch[1]=nil;

view raw splay_tree_nil.cpp hosted with ❤ by GitHub

旋轉(跟其他樹差不多)
d=0左旋,1右旋

	void rotate(node *&a,bool d){
	node *b=a;
	a=a->ch[!d];
	b->ch[!d]=a->ch[d];
	a->ch[d]=b;
	b->up();
	a->up();
	}

view raw splay_tree_rotate.cpp hosted with ❤ by GitHub

接下來是最重要的伸展操作
這是按劉汝佳在橘色那本書的寫法實現的
主要是將第k個節點伸展到root的過程
注意!! k必須大於0

	void splay(node *&o,int k){
	o->down();
	char d1=o->cmp(k);
	if(~d1){
	if(d1)k-=o->ch[0]->s+1;
	node *p=o->ch[d1];
	p->down();
	char d2=p->cmp(k);
	if(~d2){
	int k2=d2?k-p->ch[0]->s-1:k;
	splay(p->ch[d2],k2);
	if(d1==d2)rotate(o,d1^1);
	else rotate(o->ch[d1],d1);
	}
	rotate(o,d1^1);
	}
	}

view raw splay_tree_splay.cpp hosted with ❤ by GitHub

有了splay操作，接下來是分裂&合併

	/* l不能為nil */
	node *merge(node *l,node *r){
	splay(l,l->s);
	l->ch[1]=r;
	l->up();
	return l;
	}
	/* k必須 > 0 */
	void split(node *o,node *&l,node *&r,int k){
	splay(o,k);
	l=o;
	r=o->ch[1];
	o->ch[1]=nil;
	l->up();
	}

view raw splay_tree_merge_split.cpp hosted with ❤ by GitHub

當我們要維護一個區間1~n時，可以建立0~n的splay tree，0是廢棄節點，較為方便使用

最後提供新增節點的方法:

	inline node *new_node(const T&d){
	node *o=new node(d);
	o->l=o->r=nil;
	}

view raw splay_tree_new_node.cpp hosted with ❤ by GitHub

這樣所有的操作就齊全了
剩下的一些懶惰標記跟treap一樣，可以做區間翻轉和線段樹的功能
但是請小心指標的使用
(nil為衛兵指標，方便用來編輯，若不想用可以將程式碼略為修改)