數(shù)據(jù)結(jié)構(gòu)樹和鍵樹

數(shù)據(jù)結(jié)構(gòu)樹和鍵樹第1頁，課件共47頁，創(chuàng)作于2023年2月復(fù)習(xí)ABCX2LLABCX2LRABCX-2RRABCX-2RL第2頁，課件共47頁，創(chuàng)作于2023年2月復(fù)習(xí)2、已知長度為11的表{xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,yon}，按表中元素順序依次插入一棵初始為空的平衡二叉排序樹，畫出插入完成后的平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。1、按次序輸入關(guān)鍵字：7,6,5,4,3,2,1，試畫出AVL樹的構(gòu)造和調(diào)整過程。第3頁，課件共47頁，創(chuàng)作于2023年2月復(fù)習(xí)含有n個結(jié)點的二叉平衡樹能達(dá)到的最大深度：

hn=log(5(n+1))-2第4頁，課件共47頁，創(chuàng)作于2023年2月B-樹定義查找過程插入操作刪除操作查找性能的分析第5頁，課件共47頁，創(chuàng)作于2023年2月B-樹定義B-樹是一種平衡的多路查找樹：第6頁，課件共47頁，創(chuàng)作于2023年2月B-樹定義一棵m階的B-樹，或為空樹，或為滿足下列特性的m叉樹1、樹中每個結(jié)點最多有m棵子樹2、若根結(jié)點不是葉子結(jié)點，則至少有兩棵子樹3、除根之外的所有非終端（葉子）結(jié)點至少有棵子樹第7頁，課件共47頁，創(chuàng)作于2023年2月B-樹定義4、所有非終端結(jié)點中包含下列信息數(shù)據(jù)(n,A0,K1,A1,K2,A2,…,Kn,An)5、所有葉子結(jié)點都在同一層，不帶信息a.n為關(guān)鍵字的個數(shù)，多個關(guān)鍵字自小至大有序排列，即：K1<K2<…<Kn;b.且Ai-1所指子樹上所有關(guān)鍵字均小于Ki;c.Ai所指子樹上所有關(guān)鍵字均大于Ki;d.關(guān)鍵字的個數(shù)比子樹的個數(shù)小1;第8頁，課件共47頁，創(chuàng)作于2023年2月B-樹的查找過程從根結(jié)點出發(fā)，沿指針?biāo)阉鹘Y(jié)點和在結(jié)點內(nèi)進(jìn)行順序（或折半）查找兩個過程交叉進(jìn)行。若查找成功，則返回指向被查關(guān)鍵字所在結(jié)點的指針和關(guān)鍵字在結(jié)點中的位置；若查找不成功，則返回插入位置。第9頁，課件共47頁，創(chuàng)作于2023年2月B-樹的查找過程typedefstruct{BTNode*pt;//指向找到的結(jié)點的指針inti;//1..m，在結(jié)點中的關(guān)鍵字序號inttag;//標(biāo)志查找成功(=1)或失敗(=0)}Result;//在B樹的查找結(jié)果類型假設(shè)返回的是如下所述結(jié)構(gòu)的記錄:第10頁，課件共47頁，創(chuàng)作于2023年2月B-樹的查找算法ResultSearchBTree(BTreeT,KeyTypeK){

//在m階的B-樹T中查找關(guān)鍵字K,

//返回查找結(jié)果(pt,i,tag)。

//若查找成功，則特征值tag=1,

//指針pt所指結(jié)點中第i個關(guān)鍵字等于K;

//否則特征值tag=0,等于K的關(guān)鍵字應(yīng)插入在

//指針pt所指結(jié)點中第i個關(guān)鍵字

//和第i+1個關(guān)鍵字之間}//SearchBTree……第11頁，課件共47頁，創(chuàng)作于2023年2月B-樹查找算法p=T;q=NULL;found=FALSE;i=0;

while(p&&!found){n=p->keynum;i=Search(p,K);

//在p->key[1..keynum]中查找i，//使得p->key[i]<=K<p->key[i+1],//沒找到則i=-1

if(i>0&&p->key[i]==K)found=TRUE;else{q=p;p=p->ptr[i];}//q指示p的雙親}if(found)return(p,i,1);//查找成功elsereturn(q,i,0);//查找不成功第12頁，課件共47頁，創(chuàng)作于2023年2月B-樹插入結(jié)點在查找不成功之后，需進(jìn)行插入。顯然，關(guān)鍵字插入的位置必定在最下層的葉子結(jié)點，有下列幾種情況：1）插入后，該結(jié)點的關(guān)鍵字個數(shù)n<m，不需要修改指針;如插入關(guān)鍵字6050204080

6080第13頁，課件共47頁，創(chuàng)作于2023年2月B-樹插入結(jié)點2）插入后，該結(jié)點的關(guān)鍵字個數(shù)n=m，則需進(jìn)行“結(jié)點分裂”：

令s=m/2a.在原結(jié)點中保留

（A0，K1，。。。，Ks-1，As-1）；b.建新結(jié)點

（As，Ks+1，。。。，Kn，An）；c.將（Ks，p）插入雙親結(jié)點第14頁，課件共47頁，創(chuàng)作于2023年2月B-樹插入結(jié)點502040

6080再插入關(guān)鍵字90

60809060905080第15頁，課件共47頁，創(chuàng)作于2023年2月8030B-樹插入結(jié)點3）若雙親為空，則建新的根結(jié)點。204060905080再插入關(guān)鍵字302030

402040

30508050第16頁，課件共47頁，創(chuàng)作于2023年2月B-樹刪除結(jié)點刪除操作和插入結(jié)點的考慮相反1）首先必須找到待刪關(guān)鍵字所在結(jié)點，并且要求刪除之后，結(jié)點中關(guān)鍵字的個數(shù)不能小于m/2-12）否則，要從其左(或右)兄弟結(jié)點“借調(diào)”關(guān)鍵字3）若其左和右兄弟結(jié)點均無關(guān)鍵字可借(結(jié)點中只有最少量的關(guān)鍵字),則必須進(jìn)行結(jié)點的“合并”。第17頁，課件共47頁，創(chuàng)作于2023年2月B-樹刪除結(jié)點1.被刪除結(jié)點上關(guān)鍵字個數(shù)不少于m/2-1，那么只需從該結(jié)點上刪除該關(guān)鍵字Ki和相應(yīng)的指針Ai。例如下圖3-階B樹中刪除關(guān)鍵字12時，直接將12刪除即可。539024501003

12

374561703abcdefgh第18頁，課件共47頁，創(chuàng)作于2023年2月B-樹刪除結(jié)點2.如果被刪除結(jié)點上關(guān)鍵字個數(shù)等于m/2-1，而與其相鄰的右兄弟結(jié)點（或左兄弟）結(jié)點中關(guān)鍵字的個數(shù)大于m/2-1上圖為刪除50前、后的3階B-樹。53902450100337456170abcdefgh70619053第19頁，課件共47頁，創(chuàng)作于2023年2月B-樹刪除結(jié)點3.被刪除關(guān)鍵字所在結(jié)點和其相鄰的右兄弟結(jié)點（或左兄弟）結(jié)點中關(guān)鍵字的個數(shù)均等于m/2-1，9061902410033745abcdefgh7053刪除關(guān)鍵字5361

70第20頁，課件共47頁，創(chuàng)作于2023年2月90B-樹刪除結(jié)點2410033745abcdegh練習(xí)：從上面的B樹中刪除關(guān)鍵字3761

70第21頁，課件共47頁，創(chuàng)作于2023年2月^^24^3^3^2490B-樹刪除結(jié)點1003745abcdegh練習(xí)：從上面的B樹中刪除關(guān)鍵字3761

7037沒有右兄弟且其左兄弟也只有一個關(guān)鍵字，把37雙親結(jié)點中小于37的關(guān)鍵字24與左兄弟中的3合并成一個結(jié)點。此時，發(fā)現(xiàn)左右子樹高度不同，必須調(diào)整成B-樹。4590100ech32461

70g第22頁，課件共47頁，創(chuàng)作于2023年2月4590B-樹刪除結(jié)點100ech練習(xí)：從上面的B樹中刪除關(guān)鍵字37^3^24^61

70g調(diào)整后的B-樹，如下所示第23頁，課件共47頁，創(chuàng)作于2023年2月B-樹查找性能分析在B-樹中進(jìn)行查找時，其查找時間主要花費在搜索結(jié)點（訪問外存）上，即主要取決于B-樹的深度。問：1）含N個關(guān)鍵字的m階B-樹可能達(dá)到的最大深度H為多少？第24頁，課件共47頁，創(chuàng)作于2023年2月B-樹查找性能分析2）深度為H的B-樹中，至少含有多少個結(jié)點？第2層2個先推導(dǎo)每一層所含最少結(jié)點數(shù)：第1層

1個第H+1層2(m/2)H-1個第4層2(m/2)2個第3層2m/2個

……第25頁，課件共47頁，創(chuàng)作于2023年2月B-樹查找性能分析假設(shè)m階B-樹的深度為H+1，由于第H+1層為葉子結(jié)點，而當(dāng)前樹中含有N個關(guān)鍵字，則葉子結(jié)點必為N+1個，N+1≥2(m/2)H-1H-1≤logm/2((N+1)/2)H≤logm/2((N+1)/2)+1由此可推得下列結(jié)果：第26頁，課件共47頁，創(chuàng)作于2023年2月B-樹查找性能分析在含n個關(guān)鍵字的B-樹上進(jìn)行一次查找，需訪問的結(jié)點個數(shù)不超過

logm/2((n+1)/2)+1結(jié)論：第27頁，課件共47頁，創(chuàng)作于2023年2月B+樹特點是B-樹的一種變型。1）有n棵子樹的結(jié)點中含有n個關(guān)鍵字2）所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，并且，所有葉子結(jié)點彼此相鏈接構(gòu)成一個有序鏈表，其頭指針指向含最小關(guān)鍵字的結(jié)點；3）每個非葉結(jié)點中的關(guān)鍵字Ki即為其相應(yīng)指針Ai所指子樹中關(guān)鍵字的最大值；第28頁，課件共47頁，創(chuàng)作于2023年2月5096155062

78

96717884

89

965662202643503815sqrootB+樹特點第29頁，課件共47頁，創(chuàng)作于2023年2月B+樹查找過程1）在B+樹上，既可以進(jìn)行縮小范圍的查找，也可以進(jìn)行順序查找；2）在進(jìn)行縮小范圍的查找時，不管成功與否，都必須查到葉子結(jié)點才能結(jié)束；3）若在結(jié)點內(nèi)查找時，給定值≤Ki，則應(yīng)繼續(xù)在Ai所指子樹中進(jìn)行查找；第30頁，課件共47頁，創(chuàng)作于2023年2月B+樹插入和刪除操作類似于B-樹進(jìn)行，即必要時，也需要進(jìn)行結(jié)點的“分裂”或“歸并”。第31頁，課件共47頁，創(chuàng)作于2023年2月鍵樹鍵樹的結(jié)構(gòu)特點雙鏈樹Trie樹第32頁，課件共47頁，創(chuàng)作于2023年2月鍵樹的結(jié)構(gòu)特點HAD$S$VE$E$R$E$IGH$S$表示關(guān)鍵字集合{HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS}第33頁，課件共47頁，創(chuàng)作于2023年2月鍵樹定義鍵樹又稱為數(shù)字查找樹，它是一棵度>=2的樹，其中的每個結(jié)點中不是包含一個或者幾個關(guān)鍵字，而是只包含組成關(guān)鍵字的符號。第34頁，課件共47頁，創(chuàng)作于2023年2月鍵樹的結(jié)構(gòu)特點1）關(guān)鍵字中的各個符號分布在從根結(jié)點到葉結(jié)點的路徑上，葉結(jié)點內(nèi)的符號為“結(jié)束”的標(biāo)志符。因此，鍵樹的深度和關(guān)鍵字集合的大小無關(guān);2）鍵樹被約定為是一棵有序樹，即同一層中兄弟結(jié)點之間依所含符號自左至右有序，并約定結(jié)束符‘$’小于任何其它符號。第35頁，課件共47頁，創(chuàng)作于2023年2月雙鏈樹—以二叉鏈表作存儲結(jié)構(gòu)實現(xiàn)的鍵樹結(jié)點結(jié)構(gòu):first

symbol

next分支結(jié)點infoptr

symbol

next葉子結(jié)點指向孩子結(jié)點的指針指向兄弟結(jié)點的指針指向記錄的指針typedefenum{LEAF,

BRANCH}NodeKind;//兩種結(jié)點：{葉子和分支}第36頁，課件共47頁，創(chuàng)作于2023年2月HAD$HADE$R$$ES$GH$IHEHERHEREHIGHHIS…T葉子結(jié)點分支結(jié)點含關(guān)鍵字的記錄第37頁，課件共47頁，創(chuàng)作于2023年2月雙鏈樹typedefstructDLTNode{charsymbol;

structDLTNode*next;//指向兄弟結(jié)點的指針NodeKindkind;

union{Record*infoptr;//葉子結(jié)點內(nèi)的記錄指針

structDLTNode*first;//分支結(jié)點內(nèi)的孩子鏈指針}}DLTNode,*DLTree;//雙鏈樹的類型第38頁，課件共47頁，創(chuàng)作于2023年2月雙鏈樹#defineMAXKEYLEN16//關(guān)鍵字的最大長度typedefstruct{charch[MAXKEYLEN];//關(guān)鍵字intnum;//關(guān)鍵字長度}KeysType;//關(guān)鍵字類型第39頁，課件共47頁，創(chuàng)作于2023年2月雙鏈樹查找過程假設(shè):T為指向雙鏈樹根結(jié)點的指針，K.ch[0..K.num-1]為待查關(guān)鍵字(給定值)。則查找過程中的基本操作為進(jìn)行下列比較:K.ch[i]=?p->symbol

其中:0≤i≤K.num-1，p指向雙鏈樹中某個結(jié)點第40頁，課件共47頁，創(chuàng)作于2023年2月雙鏈樹查找過程1.初始狀態(tài):p=T->first;i=0;2.若(p&&p->symbol==K.ch[i]&&i<K.num-1)則繼續(xù)和給定值的下一位進(jìn)行比較

p=p->first;i++;3.若(p&&p->symbol!=K.ch[i])則繼續(xù)在鍵樹的同一層上進(jìn)行查找p=p->next;第41頁，課件共47頁，創(chuàng)作于2023年2月雙鏈樹查找過程若(p&&p->symbol==K.ch[i]&&i==K.num-1)則查找成功，返回指向相應(yīng)記錄的指針p->infoptr4.若(p==NULL)則表明查找不成功，返回“空指針”;第42頁，課件共47頁，創(chuàng)作于2023年2月Trie樹—以多重鏈表作存儲結(jié)構(gòu)實現(xiàn)的鍵樹結(jié)點結(jié)構(gòu):分支結(jié)點葉子結(jié)點指向記錄的指針012345……

242526關(guān)鍵字指向下層結(jié)點的指針每個域?qū)?yīng)一個“字母”第43頁，課件共47頁，創(chuàng)作于2023年2月01(A)345(E)9(I)……

268(H)4(D)19(S)22(V)018(R)7(G)1905(E)THADHASHAVHEHERHEREHIGHIS葉子結(jié)點分支結(jié)點指向記錄的指針第44頁，課件共47頁，創(chuàng)作于2023年2月typedefstructTrieNode{NodeKindkind;//結(jié)點類型union{struct{KeyTypeK;Record*infoptr}lf;