數(shù)據(jù)結(jié)構(gòu)課件查找2009級

9.2查找表的樹結(jié)構(gòu)表示9.2.1二叉排序樹

9.2.2平衡二叉樹

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

二叉排序樹或為空樹，或為滿足下列條件的二叉樹:1）若左子樹不空，則左子樹上所有結(jié)點的鍵值均小于根結(jié)點的鍵值；

2）若右子樹不空，則右子樹上所有結(jié)點的鍵值均大于根結(jié)點的鍵值；

3）左子樹、右子樹為二叉排序樹；二叉排序樹不是二叉排序樹9.2.1二叉排序樹45123375390247898614512337539024789861

二叉排序樹的查找

例:在二叉排序樹中查找關(guān)鍵字為24的記錄查找成功4512337539024789861

例:在二叉排序樹中查找關(guān)鍵字為60的記錄

二叉排序樹的查找查找失敗4512337539024789861二叉排序樹的存儲typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,rchild;}BiTNode,*BiTree;Lchilddatarchild

key……

………

二叉排序樹的查找typedefstruct{KeyTypekey;…}TElemType;BiTreeSearchBST(BiTreeT,KeyTypekey){/*在根指針T所指二叉排序樹中查找關(guān)鍵字等于key的數(shù)據(jù)元素，若查找成功，則返回該記錄結(jié)點的指針，否則返回空指針*/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個關(guān)鍵字，可以構(gòu)造不同形態(tài)的二叉排序樹;對于每一棵特定的二叉排序樹，可按照平均查找長度的定義來求它的ASL值;不同形態(tài)的二叉排序樹;平均查找長度的值不同，甚至可能差別很大。4512337539024789861

二叉排序樹的查找

例查找表={45,61,12,3,37,24,90,53,98,78}45123375390247898614512337539024789861二叉排序樹的查找單支樹與順序查找相同4512337539024789861(n+1)/2二叉排序樹的查找形態(tài)比較均衡的二叉排序樹與折半查找相同（與logn同階）4512337539024789861平均查找長度:

設(shè)每種形態(tài)出現(xiàn)概率相同，查找每個關(guān)鍵字也是等概率的，則（與logn同階）二叉排序樹的查找4512337539024789861

二叉排序樹的插入40

例二叉排序樹中插入結(jié)點404512337539024789861StatusInsertBST(BiTree&T,TElemTypee){//當二叉排序樹T中不存在關(guān)鍵字等于e.key的數(shù)據(jù)元素時，插入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為空,被插結(jié)點為根結(jié)點

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

}}//InsertBSTp插入604512337539024789861StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){/*在根指針為T的二叉排序樹中查找關(guān)鍵字等于key的結(jié)點。若查找成功,返回TRUE,p指向該結(jié)點;若查找不成功,返回FALSE,p指向查找路徑的最末結(jié)點.f指向當前結(jié)點的雙親，初始調(diào)用為NULL*/if(T==NULL){p=f;returnFALSE;}//查找不成功

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

else{if(LT(key,T->data.key))//繼續(xù)查找

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

3

37

53

90

24

7898

61pp查找60

二叉排序樹的插入二叉排序樹的構(gòu)造45

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

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序樹的構(gòu)造

二叉排序樹的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序樹的構(gòu)造12

二叉排序樹的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序樹的構(gòu)造123

二叉排序樹的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序樹的構(gòu)造12337

二叉排序樹的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序樹的構(gòu)造1233724

二叉排序樹的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序樹的構(gòu)造123372490

二叉排序樹的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序樹的構(gòu)造12337249053

二叉排序樹的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序樹的構(gòu)造1233724905398

二叉排序樹的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序樹的構(gòu)造1233724905398

二叉排序樹的插入

例查找表={45,61,12,3,37,24,90,53,98,78}6145二叉排序樹的構(gòu)造123372490539878

二叉排序樹的插入

二叉排序樹的刪除

F

PPRPLfppf

F

PfpF

PPL4512337539024789861二叉排序樹的刪除P為葉子結(jié)點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中查找關(guān)鍵字等于key的數(shù)據(jù)元素，若查找成功，刪除該元素，并返回TURE，否則返回FALSEf=NULL;if(!SearchBST(T,key,f,p))returnFALSE;……//刪除p所指結(jié)點

returnTRUE;}if(!p->rchild||!p->lchild)//刪除p所指結(jié)點

//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個關(guān)鍵字的查找表,構(gòu)造的二叉排序樹不唯一，與關(guān)鍵字的插入順序有關(guān)。二叉排序樹的平均查找長度與樹的形態(tài)有關(guān)（與樹的高度有關(guān)）在隨機的情況下查找、插入、刪除的時間復雜度為Ｏ(log2n)；中序遍歷二叉排序樹，將會得到一個關(guān)鍵字的有序序列；二叉排序樹的特點適用范圍用于組織規(guī)模較小的、內(nèi)存中可以容納的數(shù)據(jù);用于表示索引表9.2.2平衡二叉樹（AVL樹）結(jié)點的平衡因子：結(jié)點的左子樹高度-右子樹的高度.平衡二叉樹:所有結(jié)點的平衡因子的絕對值不超過1的二叉排序樹.平衡二叉樹10-1000000-10-1100000-24512337539024789861非平衡二叉樹45123379024789861

平衡二叉樹的構(gòu)造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是離插入結(jié)點最近平衡因子不等于0的結(jié)點，f為a的雙親*/

s=(BiTree)malloc(sizeof(BiTNode));//建新結(jié)點

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是離插入結(jié)點最近平衡因子不等于0的結(jié)點指針

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平衡因子是否失衡，做平衡旋轉(zhuǎn)

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){//平衡旋轉(zhuǎn)后，處理旋轉(zhuǎn)子樹

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

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

/*對a為根的子樹做LL旋轉(zhuǎn)，b為旋轉(zhuǎn)后的子樹的根*/b=a->lchild;a->lchild=b->rchild;a->bf=0;bb->rchild=a;b->bf=0;}LLInsertionB0AARBLBR0A2B1BRBLARvoidRR_Lotation(AVLBTreea,AVLBTree&b){

/*對a為根的子樹做RR旋轉(zhuǎn)，b為旋轉(zhuǎn)后的子樹的根*/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除根結(jié)點和葉結(jié)點外，其它每個結(jié)點至少有m/2個子結(jié)點；至多含有m個子結(jié)點；根至少含有兩棵子樹；唯一例外的是葉結(jié)點沒有子結(jié)點;多叉樹的特性15387184566278899620264350平衡樹的特性樹中所有葉子結(jié)點均在樹中的同一層次上；15387184566278899620264350結(jié)點結(jié)構(gòu)：具有d個子結(jié)點的結(jié)點包含：

d-1

個關(guān)鍵字ki（1≤i<

d）d-1

個指向記錄的指針pi（1≤i≤n）d個指向子結(jié)點的指針Ai（0≤i≤n）每個結(jié)點中的關(guān)鍵字均自小至大排列，即：k1<k2<…<kd-1；Ai-1所指子樹上所有關(guān)鍵字均小于ki

；Ai所指子樹上所有關(guān)鍵字均大于ki；查找樹的特性Ai-1

kipiAi1538718456627889962026435024312539050617010037454階B樹3階B樹B樹的查找

查找70t

查找成功2431253905061701003745

查找28t查找失敗2431253905061701003745查找性能的分析在B樹中進行查找時，其查找時間主要花費在搜索結(jié)點(訪問外存)上，即主要取決于B樹的深度。設(shè)B樹的高度為h，那么在自頂向下檢索到葉結(jié)點的過程中可能需要進行h次讀盤。在含N個關(guān)鍵字的B樹上進行一次查找，需訪問的結(jié)點個數(shù)不超過

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樹插入保持性質(zhì)：等高、階插入——分裂分裂過程可能傳遞樹高生長一層

455390

50

24

312

371006170B樹刪除刪除—代換—借關(guān)鍵字—合并

455390

50

24

312

371006170

刪除45（代換—刪除）

455390

50

24