【文章內(nèi)容簡介】 (int x){ Node *T=rt。 while (T){ if (Tkey==x){Splay(T)。return T。} else if (xTkey)T=Tl。 else T=Tr。 } return T。 } void Insert(int x){ Node *T=rt,*fa=NULL。 while (T){ fa=T。 if (xTkey)T=Tl。 else if(xTkey)T=Tr。 else return 。//two the same keys } T=(Node*)malloc(sizeof(Node))。 Tkey=x。 Tl=Tr=NULL。 Tf=fa。 if (fa){ if (fakeyx)fal=T。 else far=T。 } Splay(T)。 } void Delete(int x){ Node *T=Find(x)。 if (NULL==T)return 。//error rt=Join(Tl,Tr)。 } Node *Maxnum(Node *t){ Node *T=t。 while (Tr)T=Tr。 Splay(T)。 return T。 } Node *Minnum(Node *t){ Node *T=t。 while (Tl)T=Tl。 Splay(T)。 return T。 } Node *Last(int x){ Node *T=Find(x)。 T=Tl。 return (Maxnum(T))。 } Node *Next(int x){ Node *T=Find(x)。 T=Tr。 return (Minnum(T))。 } Node *Join(Node *t1,Node *t2){ if (NULL==t1)return t2。 if (NULL==t2)return t1。 Node *T=Maxnum(t1)。 Tl=t2。 return T。 } void Split(int x,Node *amp。t1,Node *amp。t2){ Node *T=Find(x)。 t1=Tl。 t2=Tr。 } void Inorder(Node *T){ if (NULL==T)return 。 Inorder(Tl)。 printf(%d,Tkey)。 Inorder(Tr)。 } void _Delete(){Delete(rt)。} void Delete(Node *T){ if (NULL==T)return 。 Delete(Tl)。 Delete(Tr)。 free(T)。 }private: Node *rt。//root}。AVL樹//codevs1285 莯???//by cww97includecstdioincludeiostreamincludealgorithmdefine INF 0xfffffffdefine BASE 1000000using namespace std。int ans=0。struct Node{ int x,bf,h。//bf=balance factor,h=height Node *l,*r。}。class AVLTree{public: void Init() { rt = NULL。 } int H(Node *T){return (T==NULL)?0:Th。} int BF(Node *l,Node *r){//get balance factor if (NULL==l amp。amp。 NULL==r) return 0。 else if (NULL == l) return rh。 else if (NULL == r) return lh。 return lh rh。 } Node *Lrorate(Node *a){//left rorate Node *b。 b=ar。 ar=bl。 bl=a。 ah=max(H(al),H(ar)) + 1。 bh=max(H(bl),H(br)) + 1。 abf=BF(al,ar)。 bbf=BF(bl,br)。 return b。 } Node *Rrorate(Node *a){//right rorate Node *b。 b=al。 al=br。 br=a。 ah=max(H(al),H(ar)) + 1。 bh=max(H(bl),H(br)) + 1。 abf=BF(al,ar)。 bbf=BF(bl,br)。 return b。 } Node *LRrorate(Node *a){//left then right al = Lrorate(al)。 Node *c。 c=Rrorate(a)。 return c。 } Node *RLrorate(Node *a){//right then left ar=Rrorate(ar)。 Node *c。 c=Lrorate(a)。 return c。 } void Insert(int x){_Insert(rt,x)。} void _Insert (Node *amp。T,int x){ if (NULL==T){ T=(Node*)malloc(sizeof(Node))。 Tx=x。 Tbf=0。Th=1。 Tl=Tr=NULL。 return 。 } if (x Tx) _Insert(Tl,x)。 else if (x Tx) _Insert(Tr,x)。 else return 。 //error :the same y Th=max(H(Tl),H(Tr))+1。//maintain Tbf=BF(Tl,Tr)。 if (Tbf 1 || Tbf 1){//not balanced if (Tbf 0 amp。amp。 Tlbf 0)T=Rrorate(T)。 else if (Tbf 0 amp。amp。 Trbf 0)T=Lrorate(T)。 else if (Tbf 0 amp。amp。 Tlbf 0)T=LRrorate(T)。 else if (Tbf 0 amp。amp。 Trbf 0)T=RLrorate(T)。 } } void GetPet(int x){//get pet or person if (NULL==rt){return 。} int small=0,large=INF。 //printf(x=%d\n,x)。 int flag。 if (Find(rt,x,small,large)){ printf(find %d\n,x)。 _Delete(rt,x)。 }else if (small==0)flag=1。 else if (large==INF)flag=0。 else if (largexxsmall)flag=1。 else flag=0。 if (!flag){//choose large _Delete(rt,small)。 ans=(ans+xsmall)%BASE。 }else { _Delete(rt,large)。 ans=(ans+largex)%BASE。 } } bool Find(Node *T,int x,int amp。small,int amp。large){ if (NULL==T)return 0。 if (x==Tx)return 1。 if (xTx){ large=min(large,Tx)。 return Find(Tl,x,small,large)。 }else{ small=max(small,Tx)。 return Find(Tr,x,small,large)。 } } void _Delete(Node *amp。T,int x){ if (NULL==T)return 。 if (x Tx){//y at left _Delete(Tl,x)。 Tbf=BF(Tl,Tr)。 if (Tbf1){ if (1==Trbf)T=RLrorate(T)。 else T=Lrorate(T)。//bf==0 or 1 } }else if (x Tx){//y at right _Delete(Tr,x)。 Tbf=BF(Tl,Tr)。 if (Tbf1){ if (1==Tlbf)T=LRrorate(T)。 else T=Rrorate(T)。//bf==0 or 1 } }else {//here is x if (Tlamp。amp。Tr){//left amp。amp。right Node *t=Tl。 while (tr)t=tr。 Tx=tx。 _Delete(Tl,tx)。 Tbf=BF(Tl,Tr)。 if (Tbf1){ if (1==Trbf)T=RLrorate(T)。 else T=Lrorate(T)。//bf==0 or 1 } }else {//left || right Node *t=T。