Splay Tree

splay_tree_merge_split.cpp

/* 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();
}

splay_tree_new_node.cpp

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

splay_tree_nil.cpp

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

splay_tree_node.cpp

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;

splay_tree_rotate.cpp

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();
}

splay_tree_splay.cpp

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);
	}
}