数据结构17col advtree第13章高级树结构

2两边子树等高为0“-”表示左重-1“/”表示右重+1“\”表示 一一AVLAVL树的高度是Ｏ(logn)的，它的平均

a-=-a-=0a-=//a-a--- \a-\a-b-\a--cc1.a->bf1，则a->bf0，以a为根的子2.a->bf0，则a->bf1，以a为根的子3.a->bf1，则a->bf+2

RR型旋转以avoidRR_rotation(AVLBinNode*a,AVLBinNode*&b){b=a-a->right=b- a->bf=b->left= b->bf=}

{AVLBinNodeb=a- c=b-a->right=c->left; b->left=c->right;c->left=a; c->right=b;switch(c->bf){case-1:a->bf=0; b->bf=1;//toleft 1:a->bf=-1; b->bf=0;//toright 0a->bfb->bf0;c c->bf= b=}ababccabLL型旋转以avoidLL_rotation(AVLBinNode*a,AVLBinNode*&b){b=a-a->left=b- a->bf=b->right= b->bf=}LR型旋转以avoidLR_rotation(AVLBinNode*a,AVLBinNode*&b){b=a- c=b-a->left=c->right; b->right=c->left;c->right=a; c->left=b;switch(c->bf){case-1:a->bf=1; b->bf=0;//toleft 1:a->bf=0; b->bf=-1;//toright 0a->bfb->bf0;c就是新叶}c->bf= b=}voidins_AVLtree(AVLBinNode*&rt,BELEMkey){AVLBinNode*s,*a,*b,*f,*p,*q;boolbalanced;ints=news->element=s->left=s->right=NULL; s->bf=0;if(rt==NULL){rt=s;return;}f=NULL;a=p=rt;q=查找swhilepNULL if(p->bf!=0){a=p;f=q;q=if(s->element<q->element)p=p->left;elsep=p-}if(s->element<q->element) q->left=s;elseq->right=if(s->element<a->element){//在a的左子树p=a->left;b=p;d=-1; elsepa->right;bp;d1;while(p!=s)if(s->element<p-{p->bf=-1;p=p-}else{p->bf= p=p->right;balanced=ifa->bf0)a->bf aelseif(a->bfd0)a->bf0;else{//失衡balancedFALSE;if(d==-1){if(b->bf==-1)LL_rotation(a,elseLR_rotation(a,b); //b->bf==+1}else{if(b->bf==+1)RR_rotation(a,elseRL_rotation(a, //b->bf==-1if(!balanced)if(f==NULL)rt=b;//a为根elseif(f->lefta)f->leftb;elsef->right=b;//f->right==}}二二AVL t(0)=1,t(1)= t(2)=t(i)=t(i-1)+t(i-2)+i3log(t(i)1)13log(n (2) AVL树的高度是Ｏ(logn)级的。因此，AVL树的插入、检索效率是Ｏ(logn)级通常高度i=log2n+C13.213.2xxaeulmlmxaxaeulmlm****you*nm** 用不同的类实现分支结点和叶结点typedefchar*Attr;classCharTreeNode{//Nodebaseclasscharsymbol;//symbolofchartreevirtualboolisLeaf()=0;//ForderivedclassIntlNode:publicCharTreeNode{CharTreeNode*left,*right;//ChildrenIntlNode(constchar&sym,CharTreeNode*l,CharTreeNode*r)//Constructor{symbol=sym;left=l;right=r;boolisLeaf(){returnFALSE;}//SubclassCharTreeNode*leftchild(){returnleft;}CharTreeNode*rightchild(){returnright;}voidsetleft(CharTreeNode*leftval){left=leftval;}//setleftchildvoidsetright(CharTreeNode*rightval){right=rightval;}//setcharvalue(){returnsymbol;}// classLeafNode:publicCharTreeNode{//LeafAttrattribute; //attributepropertyCharTreeNode*right;LeafNode(constAttr&val,CharTreeNode*rightsib=NULL){attribute=val;symbol='*';right=rightsib;}boolisLeaf(){returnTRUE;}//SubclassAttr&value(){returnattribute;}//nodevalueCharTreeNode*rightchild(){returnright;}voidtraverse(CharTreeNode*rt){//Preorderif(rt==NULL)return; //Nothingtovisitif(rt->isLeaf()){ //Doleafnodecout<<"Leaf:"<<((LeafNode*)rt)-}else{ //Dointernalnodetraverse(((IntlNode*)rt)->leftchild());traverse(((IntlNode*)rt)->rightchild());}

找双链树中结点，rt为根，val为要找的Attrdoubletree_search(CharTreeNode*rt,char*val){inti=0,len; p=rt; len=strlen(val);while(p!=NULL&&i<len)while(p!=NULL&&p->symbol<val[i])p=((IntlNode*)p)->rightchild();if(p==NULL||p->symbol>val[i])returnNULL;p((IntlNode*)p)->leftchild( //继续查找下一位 if(p==returnNULL;elseif(p->isLeaf())elsereturnNULL;没有对应的}//rt为根，q为p的前驱，attribute为要插入的属性。AttrinsertLeaf(CharTreeNode*&rt,CharTreeNode*q, CharTreeNode*p,Attrattribute){CharTreeNode*s; Attrtempattr;tempattr=newchar[strlen(attribute)];strcpy(tempattr,attribute);s=newLeafNode(tempattr,p);if(q==NULL) rt=s;elseif(((IntlNode*)q)->leftchild()==p)((IntlNode*)q)->setleft(s);else((IntlNode*)q)->setright(s);return((LeafNode*)s)->value(); //rt为根，q为p的前驱，attribute为要插入的属性AttrinsertSubtree(CharTreeNode*&rt,CharTreeNode*q, CharTreeNode*p,char*val,inti,Attr{CharTreeNode*s;intlen=s=newIntlNode(val[i],NULL,p);if(q==NULL)rt=s;elseif(((IntlNode*)q)->leftchild()==p)((IntlNode*)q)->setleft(s);else((IntlNode*)q)-}for(intj=i+1;j<len;j++)p=newIntlNode(val[j],NULL,s=((IntlNode*)s)-}returninsertLeaf(rt,s,NULL,}插入普通的关键码，关键码并不需要以“*”结尾Attrdoubletree_insert(CharTreeNode*&rt,char*val,Attrattribute){inti=0,len; CharTreeNode*p,*q;p=rt; q=NULL;len=strlen(val);if(rt==NULL)returninsertSubtree(rt,q,val,i,attribute);while(p!=NULL&&i<len){while(p!=NULL&&p->symbol<{q=p=((IntlNode*)p)->rightchild( if(p!=NULL&&p->symbol=={q=p=((IntlNode*)p)->leftchild(ifilen-1i++;elseif(p-return((LeafNode*)p)->value();elsereturninsertLeaf(rt,q,p, elsereturninsertSubtree(rt,q,p,val,i,}//ofwhile(p!=NULL&&i<len)returnNULL; 设基为d(字母为d=26,数字为d(1)h(1+d)/2(2)最大存储空间为三三trietypedefcharELEM; typedefELEM*Attr;constbase=26; conststart='a';enumNodetype{leafnode,internal};classTrieNode{ //GenericnodeclassNodetypemytype;//Typeforthisnodecharsymbol; //Internalnodevalueunion{struct{//StructureforinternalnodeTrieNode*trieptr[base+1];int //thenumberof}struct{ //StructforleafnodeELEM*data; //keyofleafnodeAttrattribute;//Thepropertyof} TrieNode(constAttrval)//Constructor:{mytype=leafnode;leaf.attribute=val;TrieNode(intcnt=0){//Constructor:Internalmytype=internal;intl.count=cnt;for(inti=0;i<base+1;i++)intl.trieptr[i]=NULL;}boolisLeaf(){returnmytype==leafnode;voidtraverse(TrieNode*rt){//Preorderif(rt==NULL)return;if(rt-cout<<"Leaf:"<<rt-<<elsefor(inti=0;i<base+1;i++)}}rt为根，q为前驱，attribute为要插入的属性。AttrinsertLeaf(TrieNode*q,Attrattribute){TrieNodes=newTrieNode(attribute);q->intl.trieptr[0]=s;s->leaf.attribute=newchar[strlen(attribute)];strcpy(s->leaf.attribute,attribute);returns-}AttrinsertSubtree(TrieNode*&q,ELEM*val,intk,Attrattribute){TrieNode*s; len=strlen(val);s=newTrieNode(0);if(q==NULL)q=s;else{q->intl.trieptr[val[k]-start+1]=s;}for(intj=k+1;j<len;j++)newTrieNode(0);}returninse