1、B-樹，B+樹和鍵樹,B-樹,B+樹,鍵樹,小結(jié)和作業(yè),復(fù)習(xí),復(fù)習(xí),復(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)整過程。,復(fù)習(xí),含有 n 個結(jié)點(diǎn)的二叉平衡樹能達(dá)到的最大深度： hn = log(5 (n+1) - 2,B-樹,定義,查找過程,插入操作,刪除操作,查找性能的分析,B-樹定義,B-樹是一種

2、平衡的多路查找樹：,B-樹定義,一棵m階的B-樹，或?yàn)榭諛?，或?yàn)闈M足下列特性的m叉樹,1、樹中每個結(jié)點(diǎn)最多有m棵子樹,2、若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹,3、除根之外的所有非終端（葉子）結(jié)點(diǎn)至少有 棵子樹,B-樹定義,4、所有非終端結(jié)點(diǎn)中包含下列信息數(shù)據(jù),(n, A0, K1, A1, K2, A2, , Kn, An),5、所有葉子結(jié)點(diǎn)都在同一層，不帶信息,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;,B-樹的查找過程,從根

3、結(jié)點(diǎn)出發(fā)，沿指針?biāo)阉鹘Y(jié)點(diǎn)和在結(jié)點(diǎn)內(nèi)進(jìn)行順序（或折半）查找兩個過程交叉進(jìn)行。,若查找成功，則返回指向被查關(guān)鍵字所在結(jié)點(diǎn)的指針和關(guān)鍵字在結(jié)點(diǎn)中的位置；,若查找不成功，則返回插入位置。,B-樹的查找過程,typedef struct BTNode *pt; / 指向找到的結(jié)點(diǎn)的指針 int i; / 1.m，在結(jié)點(diǎn)中的關(guān)鍵字序號 int tag; / 標(biāo)志查找成功(=1)或失敗(=0) Result; / 在B樹的查找結(jié)果類型,假設(shè)返回的是如下所述結(jié)構(gòu)的記錄:,B-樹的查找算法,Result SearchBTree(BTree T, KeyType K) / 在m 階的B-樹T中查找關(guān)鍵字K, /返

4、回查找結(jié)果 (pt,i,tag)。 /若查找成功，則特征值tag=1, /指針pt所指結(jié)點(diǎn)中第i個關(guān)鍵字等于K; /否則特征值tag=0, 等于K的關(guān)鍵字應(yīng)插入在 /指針pt所指結(jié)點(diǎn)中第i個關(guān)鍵字 /和第 i+1個關(guān)鍵字之間 / SearchBTree, ,B-樹查找算法,p=T; q=NULL; found=FALSE; i=0; while (p / 查找不成功,B-樹插入結(jié)點(diǎn),在查找不成功之后，需進(jìn)行插入。顯然，關(guān)鍵字插入的位置必定在最下層的葉子結(jié)點(diǎn)，有下列幾種情況：,1）插入后，該結(jié)點(diǎn)的關(guān)鍵字個數(shù)nm，不需要修改指針; 如插入關(guān)鍵字60,50, 20 40 , 80 , 60 80 ,

5、B-樹插入結(jié)點(diǎn),2）插入后，該結(jié)點(diǎn)的關(guān)鍵字個數(shù) n=m， 則需進(jìn)行“結(jié)點(diǎn)分裂”：令 s = m/2 a.在原結(jié)點(diǎn)中保留 （A0，K1，。， Ks-1，As-1）； b.建新結(jié)點(diǎn) （As，Ks+1，。 ，Kn，An）； c.將（Ks，p）插入雙親結(jié)點(diǎn),B-樹插入結(jié)點(diǎn),50, 20 40 , 60 80 ,再插入關(guān)鍵字90, 60 80 90 , 60 , 90 ,50 80,80,30,B-樹插入結(jié)點(diǎn),3）若雙親為空，則建新的根結(jié)點(diǎn)。, 20 40 , 60 , 90 ,50 80,再插入關(guān)鍵字30, 20 30 40 , 20 , 40 ,30 50 80,50,B-樹刪除結(jié)點(diǎn),刪除操作和插入

6、結(jié)點(diǎn)的考慮相反 1）首先必須找到待刪關(guān)鍵字所在結(jié)點(diǎn)，并且要求刪除之后，結(jié)點(diǎn)中關(guān)鍵字的個數(shù)不能小于m/2-1 2）否則，要從其左(或右)兄弟結(jié)點(diǎn)“借調(diào)”關(guān)鍵字 3）若其左和右兄弟結(jié)點(diǎn)均無關(guān)鍵字可借(結(jié)點(diǎn)中只有最少量的關(guān)鍵字),則必須進(jìn)行結(jié)點(diǎn)的“合并”。,B-樹刪除結(jié)點(diǎn),1.被刪除結(jié)點(diǎn)上關(guān)鍵字個數(shù)不少于m/2 -1，那么只需從該結(jié)點(diǎn)上刪除該關(guān)鍵字Ki和相應(yīng)的指針Ai。 例如下圖3-階B樹中刪除關(guān)鍵字12時，直接將12 刪除即可。,53 90,24, 50 , 100 , 3 12 , 37 ,45, 61 70 , 3 ,a,b,c,d,e,f,g,h,B-樹刪除結(jié)點(diǎn),2.如果被刪除結(jié)點(diǎn)上關(guān)鍵字個

7、數(shù)等于m/2 -1，而與其相鄰的右兄弟結(jié)點(diǎn)（或左兄弟）結(jié)點(diǎn)中關(guān)鍵字的個數(shù)大于m/2 -1,上圖為刪除50前、后的3階B-樹。,53 90,24, 50 , 100 , 3 , 37 ,45, 61 70 ,a,b,c,d,e,f,g,h,70 ,61 90, 53 ,B-樹刪除結(jié)點(diǎn),3.被刪除關(guān)鍵字所在結(jié)點(diǎn)和其相鄰的右兄弟結(jié)點(diǎn)（或左兄弟）結(jié)點(diǎn)中關(guān)鍵字的個數(shù)均等于m/2 -1，,90,61 90,24, 100 , 3 , 37 ,45,a,b,c,d,e,f,g,h,70 , 53 ,刪除關(guān)鍵字53,61 70 ,90,B-樹刪除結(jié)點(diǎn),24, 100 , 3 , 37 ,45,a,b,c,d,

8、e,g,h,練習(xí)：從上面的B樹中刪除關(guān)鍵字37,61 70 ,24, 3 ,3 24,90,B-樹刪除結(jié)點(diǎn), 100 , 37 ,45,a,b,c,d,e,g,h,練習(xí)：從上面的B樹中刪除關(guān)鍵字37,61 70 ,37沒有右兄弟且其左兄弟也只有一個關(guān)鍵字， 把37 雙親結(jié)點(diǎn)中小于37 的關(guān)鍵字24 與左兄弟中的3合并成一個結(jié)點(diǎn)。 此時，發(fā)現(xiàn)左右子樹高度不同，必須調(diào)整成B-樹。,45 90, 100 ,e,c,h,3 24,61 70 ,g,45 90,B-樹刪除結(jié)點(diǎn), 100 ,e,c,h,練習(xí)：從上面的B樹中刪除關(guān)鍵字37,3 24,61 70 ,g,調(diào)整后的B-樹，如下所示,B-樹查找性能

9、分析,在B-樹中進(jìn)行查找時，其查找時間主要花費(fèi)在搜索結(jié)點(diǎn)（訪問外存）上，即主要取決于B-樹的深度。,問：1）含 N 個關(guān)鍵字的 m 階 B-樹可能達(dá)到的最大深度 H 為多少？,B-樹查找性能分析,2）深度為H的B-樹中，至少含有多少個結(jié)點(diǎn)？,第 2 層 2 個,先推導(dǎo)每一層所含最少結(jié)點(diǎn)數(shù)：,第 1 層 1 個,第 H+1 層 2(m/2) H-1 個,第 4 層 2(m/2)2 個,第 3 層 2m/2 個, ,B-樹查找性能分析,假設(shè) m 階 B-樹的深度為 H+1，由于第 H+1 層為葉子結(jié)點(diǎn)，而當(dāng)前樹中含有 N 個關(guān)鍵字，則葉子結(jié)點(diǎn)必為 N+1 個，,N+12(m/2)H-1 H-1lo

10、gm/2(N+1)/2) Hlogm/2(N+1)/2)+1,由此可推得下列結(jié)果：,B-樹查找性能分析,在含 n 個關(guān)鍵字的 B-樹上進(jìn)行一次查找，需訪問的結(jié)點(diǎn)個數(shù)不超過 logm/2(n+1)/2)+1,結(jié)論：,B+樹特點(diǎn),是B-樹的一種變型。 1）有n棵子樹的結(jié)點(diǎn)中含有n個關(guān)鍵字,2）所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，并且，所有葉子結(jié)點(diǎn)彼此相鏈接構(gòu)成一個有序鏈表，其頭指針指向含最小關(guān)鍵字的結(jié)點(diǎn)；,3）每個非葉結(jié)點(diǎn)中的關(guān)鍵字Ki 即為其相應(yīng)指針Ai 所指子樹中關(guān)鍵字的最大值；,50 96,15 50,62 78 96,71 78,84 89 96,56 6

11、2,20 26 43 50,3 8 15,sq,root,B+樹特點(diǎn),B+樹查找過程,1）在 B+ 樹上，既可以進(jìn)行縮小范圍的查找，也可以進(jìn)行順序查找；,2）在進(jìn)行縮小范圍的查找時，不管成功與否，都必須查到葉子結(jié)點(diǎn)才能結(jié)束；,3）若在結(jié)點(diǎn)內(nèi)查找時，給定值Ki，則應(yīng)繼續(xù)在 Ai 所指子樹中進(jìn)行查找；,B+樹插入和刪除操作,類似于B-樹進(jìn)行，即必要時，也需要進(jìn)行結(jié)點(diǎn)的“分裂”或“歸并”。,鍵樹,鍵樹的結(jié)構(gòu)特點(diǎn),雙鏈樹,Trie樹,鍵樹的結(jié)構(gòu)特點(diǎn),表示關(guān)鍵字集合 HAD, HAS, HAVE, HE, HER, HERE, HIGH, HIS ,鍵樹定義,鍵樹又稱為數(shù)字查找樹，它是一棵度=2的樹，其

12、中的每個結(jié)點(diǎn)中不是包含一個或者幾個關(guān)鍵字，而是只包含組成關(guān)鍵字的符號。,鍵樹的結(jié)構(gòu)特點(diǎn),1）關(guān)鍵字中的各個符號分布在從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑上，葉結(jié)點(diǎn)內(nèi)的符號為“結(jié)束”的標(biāo)志符。因此，鍵樹的深度和關(guān)鍵字集合的大小無關(guān);,2）鍵樹被約定為是一棵有序樹，即同一層中兄弟結(jié)點(diǎn)之間依所含符號自左至右有序，并約定結(jié)束符$小于任何其它符號。,雙鏈樹, 以二叉鏈表作存儲結(jié)構(gòu)實(shí)現(xiàn)的鍵樹,結(jié)點(diǎn)結(jié)構(gòu):,first symbol next,分支結(jié)點(diǎn),infoptr symbol next,葉子結(jié)點(diǎn),指向孩子結(jié)點(diǎn) 的指針,指向兄弟結(jié)點(diǎn) 的指針,指向記錄 的指針,typedef enum LEAF, BRANCH Node

13、Kind; / 兩種結(jié)點(diǎn)：葉子 和 分支,H,A,D,$,HAD,E,$,R,$,$,E,S,$,G,H,$,I,HE,HER,HERE,HIGH,HIS,T,葉子結(jié)點(diǎn),分支結(jié)點(diǎn),含關(guān)鍵字 的記錄,雙鏈樹,typedef struct DLTNode char symbol; struct DLTNode *next; / 指向兄弟結(jié)點(diǎn)的指針 NodeKind kind; union Record *infoptr; / 葉子結(jié)點(diǎn)內(nèi)的記錄指針 struct DLTNode *first; / 分支結(jié)點(diǎn)內(nèi)的孩子鏈指針 DLTNode, *DLTree; / 雙鏈樹的類型,雙鏈樹,#define

14、MAXKEYLEN 16 /關(guān)鍵字的最大長度,typedef struct char chMAXKEYLEN; / 關(guān)鍵字 int num; / 關(guān)鍵字長度 KeysType; / 關(guān)鍵字類型,雙鏈樹查找過程,假設(shè): T 為指向雙鏈樹根結(jié)點(diǎn)的指針， K.ch0.K.num-1 為待查關(guān)鍵字(給定值)。,則查找過程中的基本操作為進(jìn)行下列比較: K.chi =? p-symbol 其中:0 i K.num-1， p 指向雙鏈樹中某個結(jié)點(diǎn),雙鏈樹查找過程,1.初始狀態(tài): p=T-first; i = 0;,2.若 ( p ,3.若 ( p ,雙鏈樹查找過程,若 ( p ,Trie樹, 以多重鏈表作存

15、儲結(jié)構(gòu)實(shí)現(xiàn)的鍵樹,結(jié)點(diǎn)結(jié)構(gòu):,分支結(jié)點(diǎn),葉子結(jié)點(diǎn),指向記錄 的指針,指向下層結(jié)點(diǎn)的指針 每個域?qū)?yīng)一個“字母”,0 1(A) 3 4 5(E) 9(I) 26,8(H),4(D) 19(S) 22(V) 0 18(R) 7(G) 19,0 5(E),T,HAD,HAS,HAV,HE,HER,HERE,HIG,HIS,葉子結(jié)點(diǎn),分支結(jié)點(diǎn),指向記錄 的指針,typedef struct TrieNode NodeKind kind; / 結(jié)點(diǎn)類型 union struct KeyType K; Record *infoptr lf; / 葉子結(jié)點(diǎn)(關(guān)鍵字和指向記錄的指針) struct TrieNode *ptr27; int num bh; / 分支結(jié)點(diǎn)(27個指向下一層結(jié)點(diǎn)的指針) TrieNode, *TrieTree; / 鍵樹類型,結(jié)點(diǎn)結(jié)構(gòu)的 C 語言描述:,Trie樹,Trie樹查找過程,在 Trie 樹中查找記錄的過程:,假設(shè): T 為指向 Trie 樹根結(jié)點(diǎn)的指針， K.num是字符的個數(shù)， K.ch0.K.num-1 為待查關(guān)鍵字(給定值)。,則查找過程中的基本操作為： 搜索和對應(yīng)字母相應(yīng)的指針: 若 p 不空，且 p 所指為分支結(jié)點(diǎn)， 則 p = p-bh.Ptror