template<typename KEY,typename DATA>
struct Tnode{
	KEY key;DATA data;int sz;char b;
	Tnode *lc,*rc;
	Tnode(){lc=rc=NULL;b=0;sz=1;}
	Tnode **c(int a){return a==-1?&lc:&rc;}
};
#define ROTATE(y,x,d) *(y->c(d))=*(x->c(-(d)));*(x->c(-(d)))=y;
template<typename KEY,typename DATA>
struct AVL{
	Tnode<KEY,DATA> root;
	int H;
	AVL(){root.rc=NULL;H=0;}
	Tnode<KEY,DATA>* tIns(KEY k){
		Tnode<KEY,DATA> *t,*s,*p,*q,*r;
		int a;
		if (!root.rc){root.rc=new Tnode<KEY,DATA>;root.rc->key=k;H=1;return root.rc;}
		t=&root;s=p=root.rc;
		while (1){
			if (k<p->key){
				q=p->lc;
				if (!q){q=new Tnode<KEY,DATA>;p->lc=q;break;}
				if (q->b){t=p;s=q;}
				p=q;
			}else if (k>p->key){
				q=p->rc;
				if (!q){q=new Tnode<KEY,DATA>;p->rc=q;break;}
				if (q->b){t=p;s=q;}
				p=q;
			}else return p;
		}
		q->key=k;p=root.rc;
		while (p!=q){
			if (k<p->key){p->sz++;p=p->lc;}
			else p=p->rc;
		}
		if (k<s->key)a=-1;else a=1;
		r=p=*(s->c(a));
		while (p!=q){
			if (k<p->key){p->b=-1;p=p->lc;}
			else {p->b=1;p=p->rc;}
		}
		if (s->b==0){s->b=a;H++;return q;}
		else if (s->b==-a){s->b=0;return q;}
		else{
			if (r->b==a){
				ROTATE(s,r,a)
				s->b=r->b=0;p=r;
				if (a==1)r->sz+=s->sz;
				else if (a==-1)s->sz-=r->sz;
			}else{
				p=*(r->c(-a));
				ROTATE(r,p,-a) ROTATE(s,p,a)
				if (p->b==a){s->b=-a;r->b=0;}
				else if (p->b==0)s->b=r->b=0;
				else {s->b=0;r->b=a;}
				p->b=0;
				if (a==1){r->sz-=p->sz;p->sz+=s->sz;}
				else if (a==-1){p->sz+=r->sz;s->sz-=p->sz;}
			}
			if (s==t->rc)t->rc=p;else t->lc=p;
		}
		return q;
	}
	Tnode<KEY,DATA>* Find(KEY k){Tnode<KEY,DATA> *p;p=root.rc;
		while (p && p->key!=k)if (k<p->key)p=p->lc;else p=p->rc;
		return p;
	}
	Tnode<KEY,DATA>* Find_index(int id){Tnode<KEY,DATA> *p;p=root.rc;
		while (p && p->sz!=id+1)if (id>=p->sz){id-=p->sz;p=p->rc;}else p=p->lc;
		return p;
	}
};

• 至少多写点括号是有备无患的 (65) AllwaysLoser 2009-05-29 21:54:49