《资料结构-使用c语言2b-tree电子教案.ppt》由会员分享，可在线阅读，更多相关《资料结构-使用c语言2b-tree电子教案.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、资料结构-使用C语言2B-tree11.1 m-way搜尋樹搜尋樹何謂m-waw搜尋樹(m-way search tree)？一棵m-way搜尋樹，所有節點的分支度（dgree）均小於或等於m。若T為空樹，則T亦稱為m-way搜尋樹，倘若T不是空樹，則必須具備下列的性質：n節點的型態是n,A0,(K1,A1),(K2,A2),.,(Kn,An)其中Ai是子樹的指標 0 i n m;n為節點上的鍵值數，Ki是鍵值1 i n 及 1 n m。211.1 m-way搜尋樹搜尋樹n節點中的鍵值是由小至大排列的，因此 Ki Ki+1，1 i n。n子樹Ai的所有鍵值均小於鍵值Ki+1但大於Ki，0 i
2、1必須滿足以下的特性：n樹根至少有二個子節點（children），亦即節點內至少有一鍵值（key value）。n除了樹根外，所有節點至少有個子節點，至多有m個子節點。此表示至少應有-1個鍵值，至多有m-1個鍵值（表示大於m/2的最小正整數）。n所有的樹葉節點皆在同一階層。1411.2 B-tree1511.2 B-tree在圖11-2中(a)不屬於B-tree of order 3，因為樹葉節點不在同一階層上，而(b)是屬於B-tree of order 3，因為所有的樹葉節點皆在同一階層。B-tree of order 3表示除了樹葉節點外每一節點的分支度（degree）不是等於2就是等於
3、3，因此B-tree of order 3就是著名的2-3 tree。假使m=4，則是2-3-4 tree。1611.2 B-tree11.2.1 B-tree 的加入假設加入P節點，若n該節點少於m-1個鍵值。n該節點的鍵值已等於m-1，則將此節點分為二，因為一棵order為m的B-tree，最多只能有m-1個鍵值。1711.2 B-tree請看下例之說明（此處的B-tree為order 5）1811.2 B-tree加入88於圖11-31911.2 B-tree承(1)加入982011.2 B-tree承(2)加入912111.2 B-tree承(3)加入932211.2 B-tree承(
4、4)加入992311.2 B-tree11.2.2 B-tree的刪除B-tree的刪除與2-3 tree和2-3-4 tree的刪除基本上原理是相同的，此處也分成兩部份：n刪除的節點是樹葉節點（leaf node），n刪除的節點為非樹葉節點（non-leaf node）。2411.2 B-tree以B-tree of order 5如圖11-4來說明。2511.2 B-tree若刪除的節點是樹葉節點若刪除的節點是樹葉節點如將圖11-4刪除702611.2 B-treen如欲將圖11-4中的鍵值26刪除2711.2 B-treen若欲刪除852811.2 B-treen有一棵B-tree of
5、 order 5如圖11-5所示2911.2 B-tree先從圖11-5刪除593011.2 B-tree由於合併後c節點僅存放一個鍵值，不符合B-tree的定義3111.2 B-tree若刪除的節點為非樹葉節點若刪除的節點為非樹葉節點3211.2 B-tree若刪除圖11-6的鍵值50，找到p節點為g，從中取出最小值52，並代替50。3311.2 B-tree若再刪除523411.2 B-tree承上圖，若繼續刪除553511.2 B-tree由於g節點其鍵值數少於 個鍵值，且其兄弟節點h也沒有大於 個鍵值，故將g、h、與c的鍵值65合併於g節點，結果如下圖：3611.2 B-tree此時c節點的鍵值數也少於 ，且其兄弟節點的鍵值數不大於 ，故將b、c與a節點合併，結果如下：37此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢