深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017-B-樹演示文檔
《深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017-B-樹演示文檔》由會員分享,可在線閱讀,更多相關(guān)《深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017-B-樹演示文檔(19頁珍藏版)》請在裝配圖網(wǎng)上搜索。
.,B-樹,前面討論的查找算法都是在內(nèi)存中進(jìn)行的,它們適用于較小的文件,而對較大的、存放在外存儲器上的文件就不合適了。 1972年R.Bayer和E.M.McCreight提出了一種稱為B-樹的多路平衡查找樹,它適合在磁盤等直接存取設(shè)備上組織動態(tài)的查找表。,一. B-樹的定義,B-樹是一種平衡的多路查找樹,在文件系統(tǒng)中,成為索引文件的一種有效結(jié)構(gòu),得到廣泛應(yīng)用。,.,一棵m階(m3)B-樹,或為空樹,或為滿足下列特性的m叉樹:(1)樹中每個結(jié)點至多有m棵子樹;(2)若根結(jié)點不是葉子結(jié)點,至少有兩棵子樹;(3)所有的非終端結(jié)點中包含下列信息 (n,p0,k1,p1,k2,p2,kn,pn)其中:ki(1in)為關(guān)鍵字,且kiki+1(1in); pj(0jn)為指向子樹根結(jié)點的指針,且pj(0jn)所指子樹中所有結(jié)點的關(guān)鍵字均小于kj+1,pn所指子樹中所有結(jié)點的關(guān)鍵字均大于kn,n(m/2-1nm-1)為關(guān)鍵字的個數(shù)(n+1為子樹個數(shù))。,B-樹,.,(4)除根結(jié)點之外所有非終端結(jié)點至少有m/2棵子樹,也即每個非根結(jié)點至少應(yīng)有m/2-1個關(guān)鍵字;(5)所有的葉子結(jié)點都出現(xiàn)在同一層上,并且不帶信息(可看作外部結(jié)點或查找失敗的結(jié)點,這些結(jié)點不存在,指向這些結(jié)點的指針為空)。,B-樹,.,2 50 80,root,2 20 40,2 55 70,例一棵3階的B-樹,B-樹,.,B-樹的基本操作,B-樹的查找運算,2 50 80,root,2 20 40,2 55 70,.,B-樹的插入運算,在B-樹中插入關(guān)鍵字k的方法:首先在樹中查找k,找到,直接返回(假設(shè)不處理相同關(guān)鍵字的插入);否則查找操作必失敗于某個葉子結(jié)點上,可以確定關(guān)鍵字k的插入位置,將k插入到所指葉結(jié)點位置上。若該葉結(jié)點原來非滿(結(jié)點中原有關(guān)鍵字總數(shù)小于m-1),則插入k并不會破壞B-樹的性質(zhì),故插入操作完成,例如,在下圖所示5階B-樹的某結(jié)點(假設(shè)為p結(jié)點)中插入新的關(guān)鍵字150時的結(jié)果。,B-樹的基本操作,.,2 100 190,3 100 150 190,在關(guān)鍵字個數(shù)不滿的結(jié)點中插入關(guān)鍵字,若p所指示的葉結(jié)點原為滿,則插入后破壞了B-樹的性質(zhì)(1),須調(diào)整使其維持B-樹的性質(zhì)不變。,B-樹的基本操作,.,調(diào)整方法:將違反性質(zhì)(1)的結(jié)點以中間位置的關(guān)鍵字keym/2為劃分點,將該結(jié)點(即p)(m,p0,k1,p1,km,pm)分裂為兩個結(jié)點左邊:(m/2-1,p0,k1,km/2-1,pm/2-1)右邊:(m-m/2,pm/2,km/2+1,km,pm)同時把中間關(guān)鍵字km/2插入到雙親結(jié)點中。于是雙親結(jié)點中指向被插入結(jié)點的指針pre改成pre、km/2、pre三部分。指針pre指向分裂后的左邊結(jié)點,指針pre指向分裂后的右邊結(jié)點。由于將km/2插入雙親時,雙親結(jié)點亦可能原本為滿,若如此,則需對雙親做分裂操作。分裂過程的例子如圖所示。,B-樹的基本操作,.,2 80 220,4 90 120 140 160,p,3 80 120 220 ,2 90 100,2 140 160,pre,pre,pre,km/2,插入100以前,插入100以后,B-樹的基本操作,.,例如初始時B-樹為空樹,通過逐個向B-樹中插入新結(jié)點,可生成一棵B-樹。下圖說明了一棵5階B-樹的生長過程。,6 8 15 16,6 8,15,16 22,6 8 10,15,16 18 22 32,(a)插入6、8、15、16 (b)插入22 (c)插入10、18、32,6 8 10,15 20,16 18,22 32,6 8 10 12,15 20,16 18 19,22 32 40 50,6 8 10 12,15 20 40,16 18 19,22 32,50 56,(d)插入20 (e)插入12、19、40、50 (f)插入56,B-樹的基本操作,.,6 8,9 15 20 40,16 18 19,22 26 32 36,50 52 55 56,10 12,6 8,9 15,16 18 19,22 26,50 52 55 56,10 12,36 38,20,32 40,(g)插入9、26、36、52、55 (h)插入38,.,B-樹的基本操作,B-樹的刪除運算,在B-樹上刪除一個關(guān)鍵字,首先找到該關(guān)鍵字所在結(jié)點及其在結(jié)點中的位置??煞譃閮煞N情況:(1)被刪除結(jié)點ki在最下層的非終端結(jié)點(即葉子結(jié)點的上一層),則刪除ki及它右邊的指針pi。 刪除后若結(jié)點中關(guān)鍵字?jǐn)?shù)目不少于m/2-1,刪除完成,否則進(jìn)行“合并”結(jié)點的操作。(2)若刪結(jié)點ki是最下層的非終端結(jié)點以上某層的結(jié)點,根據(jù)B-樹的特性可知,可以用ki右邊指針pi所指子樹中最小關(guān)鍵字y代替ki,然后在相應(yīng)的結(jié)點中刪除y,或用ki左邊指針pi-1所指子樹中最大關(guān)鍵字x代替ki,然后在相應(yīng)的結(jié)點中刪除x。,.,例 :刪除圖所示3階B-樹中的關(guān)鍵字50,可以用它右邊指針?biāo)缸訕渲凶钚£P(guān)鍵字60代替50,爾后轉(zhuǎn)化為刪除葉子上面一層的結(jié)點中的60,刪除后得到的B-樹如圖所示。,.,90 115,8,40,28,150 200,85 120,50,60 80,90 115,8,40,28,150 200,85 120,60,80,3階B-樹中刪除50以60代替50,.,刪除B-樹葉子上面一層結(jié)點中的關(guān)鍵字的方法,分三種情形:,1)被刪關(guān)鍵字所在葉子上面一層結(jié)點中的關(guān)鍵字?jǐn)?shù)目不小于m/2,則只需要從該結(jié)點中刪去關(guān)鍵字ki和相應(yīng)的指針pi,樹的其它部分不變。,例:,刪除60與115,.,2)被刪關(guān)鍵字所在葉子上面一層結(jié)點中的關(guān)鍵字?jǐn)?shù)目等于m/2-1,而與該結(jié)點相鄰的右兄弟結(jié)點(或左兄弟結(jié)點)中的關(guān)鍵字?jǐn)?shù)目大于m/2-1,則需要將其右兄弟的最小關(guān)鍵字(或其左兄弟的最大關(guān)鍵字)移至雙親結(jié)點中,而將雙親結(jié)點中小于(或大于)該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在的結(jié)點中。例如從圖中刪除關(guān)鍵字90,結(jié)果如圖所示。,.,3)被刪關(guān)鍵字所在葉子上面一層結(jié)點中的關(guān)鍵字?jǐn)?shù)和其相鄰的兄弟結(jié)點中的關(guān)鍵字?jǐn)?shù)目均等于m/2-1,則第(2)種情況中采用的移動方法將不奏效,此時須將被刪關(guān)鍵字所有結(jié)點與其左或右兄弟合并。不妨設(shè)該結(jié)點有右兄弟,但其右兄弟地址由雙親結(jié)點指針pi所指,則在刪除關(guān)鍵字之后,它所在結(jié)點中剩余的關(guān)鍵字和指針加上雙親結(jié)點中的關(guān)鍵字ki一起合并到pi所指兄弟結(jié)點中(若沒有右兄弟,則合并至左兄弟結(jié)點中)。,.,例刪去關(guān)鍵字120,則應(yīng)刪去120所在結(jié)點,并將雙親結(jié)點中的150與200合并成一個結(jié)點,刪除后的樹如圖所示。如這一操作使雙親結(jié)點中的關(guān)鍵字?jǐn)?shù)目小于m/2-1,則依同樣方法進(jìn)行調(diào)整,最壞的情況下,合并操作會向上傳播至根,當(dāng)根中只有一個關(guān)鍵字時,合并操作將會使根結(jié)點及其兩個孩子合并成一個新的根,從而使整棵樹的高度減少一層。,.,例刪除關(guān)鍵字8關(guān)鍵字所在結(jié)點無左兄弟,只檢查其右兄弟,然而右兄弟關(guān)鍵字?jǐn)?shù)目等于m/2-1,此時應(yīng)檢查其雙親結(jié)點關(guān)鍵字?jǐn)?shù)目是否大于等于m/2-1,但此處其雙親結(jié)點的關(guān)鍵字?jǐn)?shù)目等于m/2-1,從而進(jìn)一步檢查雙親結(jié)點兄弟結(jié)點關(guān)鍵字?jǐn)?shù)目是否均等于m/2-1,這里關(guān)鍵字28所在的結(jié)點的右兄弟結(jié)點關(guān)鍵字?jǐn)?shù)目正好等于m/2-1,因此將28和40結(jié)合成一個結(jié)點,50和85結(jié)合成一個結(jié)點,使得樹變矮,刪除結(jié)點8后的結(jié)果如圖所示。,- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
10 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該PPT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 深圳大學(xué) 數(shù)據(jù)結(jié)構(gòu) 2017 演示 文檔
鏈接地址:http://appdesigncorp.com/p-359904.html