数据结构课件查找2009级

9.2查找表的树结构表示9.2.1二叉排序树

9.2.2平衡二叉树

9.2.3B树、B+树9.2.1二叉排序树

二叉排序树或为空树，或为满足下列条件的二叉树:1）若左子树不空，则左子树上所有结点的键值均小于根结点的键值；

2）若右子树不空，则右子树上所有结点的键值均大于根结点的键值；

3）左子树、右子树为二叉排序树；二叉排序树不是二叉排序树9.2.1二叉排序树45123375390247898614512337539024789861

二叉排序树的查找

例:在二叉排序树中查找关键字为24的记录查找成功4512337539024789861

例:在二叉排序树中查找关键字为60的记录

二叉排序树的查找查找失败4512337539024789861二叉排序树的存储typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,rchild;}BiTNode,*BiTree;Lchilddatarchild

key……

………

二叉排序树的查找typedefstruct{KeyTypekey;…}TElemType;BiTreeSearchBST(BiTreeT,KeyTypekey){/*在根指针T所指二叉排序树中查找关键字等于key的数据元素，若查找成功，则返回该记录结点的指针，否则返回空指针*/if(T==NULL||(EQ(key,T->data.key))returnT;else{if(LT(key,T->data.key)) return(SearchBST(T->lchild,key)); elsereturn(SearchBST(T->rchild,key));}}//SearchBST二叉排序树的查找(递归算法)二叉排序树的查找查找性能的分析

n个关键字，可以构造不同形态的二叉排序树;对于每一棵特定的二叉排序树，可按照平均查找长度的定义来求它的ASL值;不同形态的二叉排序树;平均查找长度的值不同，甚至可能差别很大。4512337539024789861

二叉排序树的查找

例查找表={45,61,12,3,37,24,90,53,98,78}45123375390247898614512337539024789861二叉排序树的查找单支树与顺序查找相同4512337539024789861(n+1)/2二叉排序树的查找形态比较均衡的二叉排序树与折半查找相同（与logn同阶）4512337539024789861平均查找长度:

设每种形态出现概率相同，查找每个关键字也是等概率的，则（与logn同阶）二叉排序树的查找4512337539024789861

二叉排序树的插入40

例二叉排序树中插入结点404512337539024789861StatusInsertBST(BiTree&T,TElemTypee){//当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TURE，否则返回FALSEif(SearchBST(T,e.key,NULL,p))returnFALSE;else{//查找不成功，插入

s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=NULL;s->rchild=NULL;if(T==NULL)T=s;//T为空,被插结点为根结点

elseif(LT(e.key,p->data.key))p->lchild=s; elsep->rchild=s;returnTRUE;//插入成功

}}//InsertBSTp插入604512337539024789861StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){/*在根指针为T的二叉排序树中查找关键字等于key的结点。若查找成功,返回TRUE,p指向该结点;若查找不成功,返回FALSE,p指向查找路径的最末结点.f指向当前结点的双亲，初始调用为NULL*/if(T==NULL){p=f;returnFALSE;}//查找不成功

if(EQ(T->data.key,key)){p=T;returnTRUE;}//查找成功

else{if(LT(key,T->data.key))//继续查找

return(SearchBST(T->lchild,key,T,p));else return(SearchBST(T->rchild,key,T,p));}}//SearchBST4512

3

37

53

90

24

7898

61pp查找60

二叉排序树的插入二叉排序树的构造45

例查找表={45,61,12,3,37,24,90,53,98,78}

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序树的构造

二叉排序树的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序树的构造12

二叉排序树的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序树的构造123

二叉排序树的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序树的构造12337

二叉排序树的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序树的构造1233724

二叉排序树的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序树的构造123372490

二叉排序树的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序树的构造12337249053

二叉排序树的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序树的构造1233724905398

二叉排序树的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序树的构造1233724905398

二叉排序树的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序树的构造123372490539878

二叉排序树的插入

二叉排序树的删除

F

PPRPLfppf

F

PfpF

PPL4512337539024789861二叉排序树的删除P为叶子结点pf

F

P删除前f

F删除后p4512337539024789861f45123375390247861f二叉排序树的删除P只有左子树PL或只有右子树PR删除后f

FPLfpF

PPL删除前p45123375390247861f451233753782461f二叉排序树的删除P既有左子树PL也有右子树PRF

PQSSLQLCLCPR312612437785345二叉排序树的删除451233753782461P既有左子树PL也有右子树PR31261243778455337中序序列二叉排序树的删除4512337537824614512337537824613712337537824613712324537861P既有左子树PL也有右子树PRF

PQ

SSLQLCLCPR删除前二叉排序树的删除F

SQ

SSLQLCLCPRF

SQQLCLCPR

删除后SLP既有左子树PL也有右子树PRStatusDeleteBST(BiTree&T,KeyTypekey){//在二叉排序树T中查找关键字等于key的数据元素，若查找成功，删除该元素，并返回TURE，否则返回FALSEf=NULL;if(!SearchBST(T,key,f,p))returnFALSE;……//删除p所指结点

returnTRUE;}if(!p->rchild||!p->lchild)//删除p所指结点

//p没有右子树或没有左子树

{if(!p->rchild)s=p->lchild;//p没有右子树

elseif(!p->lchild)s=p->rchild;//p没有左子树

if(f==NULL){T=s;free(p);}//p没有双亲

elseif(f->lchild==p){f->lchild=s;free(p);}else{f->rchild=s;free(p);}}else……}删除后f

FPLfpF

PPL删除前sselse//既有右子树又有左子树

{q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;free(s);}returnTRUE;}//DeleteBSTF

PQ

SSLQLCL

CPRF

PSL

SPRF

S

SLPRSPRFCQQLSLCLsqsq=pq=psp=q二叉排序树的特点对含有n个关键字的查找表,构造的二叉排序树不唯一，与关键字的插入顺序有关。二叉排序树的平均查找长度与树的形态有关（与树的高度有关）在随机的情况下查找、插入、删除的时间复杂度为Ｏ(log2n)；中序遍历二叉排序树，将会得到一个关键字的有序序列；二叉排序树的特点适用范围用于组织规模较小的、内存中可以容纳的数据;用于表示索引表9.2.2平衡二叉树（AVL树）结点的平衡因子：结点的左子树高度-右子树的高度.平衡二叉树:所有结点的平衡因子的绝对值不超过1的二叉排序树.平衡二叉树10-1000000-10-1100000-24512337539024789861非平衡二叉树45123379024789861

平衡二叉树的构造LL型平衡处理（右旋）RR型平衡处理（左旋）LR型平衡处理（先左后右）RL型平衡处理（先右后左）ABBRXBLABBRXBLCLXCRXABCCLXCRXABC例查找表{10,13,19,7,4,8,15,24,33,21}101319ABBR191013ABBR插入10、13、19A1B0BLBRALRRInsertionRRRotationA2B1BLBRALBLB0AALBR0

插入7、419713410ABC19101374ABCA1B0BRBLARLLInsertionA2B1BRBLARLLRotationB0AARBLBR01200000000197481013ABC197134108ABC

插入8191013748ABCA1B0BLARC0CRCLLRInsertionA2B1BLARC1CRCLORLRRotationBLARC0A1or0CRB0or1CLOR19748151013ABC81074151319ABC

插入1510741319158ABCA1B0BRALC0CLCRRLInsertionA2B1BRALC1CLCRORRLRotationBRALC0A0or1CLB1or0CROR8107

415

13

1933

24ABRB8107415

13

24

1933AB

插入24、33BRRR型平衡处理（右旋）ABC

218

1074

15

13

24

19

33ABC

3381074

15

13

19

24ABC

2181074

19

15

24

13

33

插入21RL型平衡处理（先右后左）voidins_AVLTree(AVLBNode&T,KeyTypekey){/*p当前点，q为p的双亲，a是离插入结点最近平衡因子不等于0的结点，f为a的双亲*/

s=(BiTree)malloc(sizeof(BiTNode));//建新结点

s->data=key;s->lchild=NULL;s->rchild=NULL;

s->bf=0;if(T==NULL){T=s;return;}f=NULL;a=p=T;q=NULL;//查找s的插入位置

while(p!=NULL){//查找插入位置

if(p->bf!=0){a=p;f=q;}

//a是离插入结点最近平衡因子不等于0的结点指针

q=p;if(s->data<p->data)p=p->lchild;elsep=p->rchild;}//whileif(s->data<q->data)//插入sq->lchild=s;elseq->rchild=s;if(s->data<a->data)p=a->lchild;b=p;d=-1;//s在a的左子树,b为a的左孩子

elsep=a->rchild;b=p;d=1;//s在a的右子树,b为a的右孩子

while(p!=s){//修改a的子树的平衡因子

if(s->data<p->data){p->bf=-1;p=p->lchild;}//s在p的左子树

else{p->bf=1;p=p->rchild;}//s在p的右子树

}

//判断a平衡因子是否失衡，做平衡旋转

balance=TRUE;if(a->bf==0)a->bf=d;elseif(a->bf+d==0)a->bf=0;else{//a平衡因子失衡,balanced=FALSE;if(d=-1)//s在a的左子树

if(b->df==-1)LL_Lotation(a,b);elseLR_Lotation(a,b);//b->bf==1

elseif(b->df==1)RR_Lotation(a,b);elseRL_Lotation(a,b);//b->bf==-1if(!balanced){//平衡旋转后，处理旋转子树

if(f==NULL)T=b;//a为根

elseif(f->lchild==a)f->lchild=b;elsef->rchild=b;}}voidLL_Lotation(AVLBTreea,AVLBTree&b){

/*对a为根的子树做LL旋转，b为旋转后的子树的根*/b=a->lchild;a->lchild=b->rchild;a->bf=0;bb->rchild=a;b->bf=0;}LLInsertionB0AARBLBR0A2B1BRBLARvoidRR_Lotation(AVLBTreea,AVLBTree&b){

/*对a为根的子树做RR旋转，b为旋转后的子树的根*/b=a->rchild;a->rchild=b->lchild;b->lchild=a;b->bf=0;}voidLR_Lotation(AVLBTreea,AVLBTree&b){b=a->lchild;c=b->rchild;a->lchild=c->rchild;b->rchild=c->lchild;c->rchild=a;c->lchild=b;switch(c->bf)case–1:a->bf=1;b->bf=0;break;//tolchildcase1:a->bf=0;b->bf=-1;break;//torchildcase0:a->bf=b->bf=0;break;//c是叶子

}c->bf=0;b=c;}voidRL_Lotation(AVLBTreea,AVLBTree&b){b=a->rchild;c=b->lchild;a->rchild=c->lchild;b->lchild=c->rchild;c->lchild=a;c->rchild=b;switch(c->bf)case–1:a->bf=0;b->bf=1;break;//tolchildcase1:a->bf=-1;b->bf=0;break;//torchildcase0:a->bf=b->bf=0;break;//c是叶子

}c->bf=0;b=c;}9.2.3B树和B+树B树的定义B树的查找B树的插入B树的删除B+树B树的定义B树是一种平衡的多路查找树m阶B树，或为空树，或为满足的下列条件m叉树:15387184566278899620264350除根结点和叶结点外，其它每个结点至少有m/2个子结点；至多含有m个子结点；根至少含有两棵子树；唯一例外的是叶结点没有子结点;多叉树的特性15387184566278899620264350平衡树的特性树中所有叶子结点均在树中的同一层次上；15387184566278899620264350结点结构：具有d个子结点的结点包含：

d-1

个关键字ki（1≤i<

d）d-1

个指向记录的指针pi（1≤i≤n）d个指向子结点的指针Ai（0≤i≤n）每个结点中的关键字均自小至大排列，即：k1<k2<…<kd-1；Ai-1所指子树上所有关键字均小于ki

；Ai所指子树上所有关键字均大于ki；查找树的特性Ai-1

kipiAi1538718456627889962026435024312539050617010037454阶B树3阶B树B树的查找

查找70t

查找成功2431253905061701003745

查找28t查找失败2431253905061701003745查找性能的分析在B树中进行查找时，其查找时间主要花费在搜索结点(访问外存)上，即主要取决于B树的深度。设B树的高度为h，那么在自顶向下检索到叶结点的过程中可能需要进行h次读盘。在含N个关键字的B树上进行一次查找，需访问的结点个数不超过

logm/2((N+1)/2)+1B树插入插入——分裂

455390

50

24

312

3710061703阶B树

插入30

455390

50

24

312

371006170

455390

50

24

31230

371006170

插入26-分裂

455390

50

24

31230371006170

3

12

26

37

455390

5024301006170

插入85

45

50100

85

61537090

3

12

26

37

2430

3

12

26

37

455390

5024301006170

插入85

45

70

50100

85

61

53

90

3

12

26

37

2430

45

50100

85

61537090

3

12

26

37

2430B树插入保持性质：等高、阶插入——分裂分裂过程可能传递树高生长一层

455390

50

24

312

371006170B树删除删除—代换—借关键字—合并

455390

50

24

312

371006170

删除45（代换—删除）

455390

50

24