[ 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