[ 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