欧美性猛交XXXX免费看蜜桃,成人网18免费韩国,亚洲国产成人精品区综合,欧美日韩一区二区三区高清不卡,亚洲综合一区二区精品久久

打開(kāi)APP
userphoto
未登錄

開(kāi)通VIP，暢享免費電子書(shū)等14項超值服

開(kāi)通VIP

首頁(yè)

好書(shū)

留言交流

下載APP

聯(lián)系客服
B樹(shù)的C實(shí)現

                                              從B樹(shù)談到R樹(shù)之B樹(shù)的C實(shí)現

作者：weedge，July。編程藝術(shù)室出品。

前言

    代碼大全的作者Steve McConnell曾稱(chēng)，他所見(jiàn)識的任何一本書(shū)都不是某一個(gè)人能完全獨立即能完成的。吾深以為然。

    本blog內的文章十有八九系我個(gè)人參考資料原創(chuàng )所作，與此同時(shí)十有二三系本人與吾的朋友共同創(chuàng )作完成。所以，諸君在瀏覽本博客內任何一篇文章時(shí)，務(wù)必尊重他人勞動(dòng)成果。當然，有任何問(wèn)題，歡迎隨時(shí)不吝指正。

    ok，在本blog之前的一篇文章中：從B樹(shù)、B+樹(shù)、B*樹(shù)談到R 樹(shù)，各位讀者反應熱烈。這次，咱們來(lái)編碼實(shí)現B樹(shù)的查找，插入，刪除等操作。同時(shí)此文也算作是上一篇文章從B樹(shù)談到R樹(shù)的續。望諸君不吝賜教。謝謝。

第一部分、B樹(shù)的查找，插入，刪除等具體操作

    編碼實(shí)現B樹(shù)之前，咱們先來(lái)回顧一下上文中所給出的B樹(shù)的查找，插入，刪除等具體的操作都是怎么一回事兒。明白了原理之后，再來(lái)編程實(shí)現，就相對來(lái)說(shuō)有方向感了。ok，請看下文（援引自從B樹(shù)、B+樹(shù)、B*樹(shù)談到R 樹(shù)第3小節）：

B樹(shù)的插入、刪除操作

    上文第3小節簡(jiǎn)單介紹了利用B樹(shù)這種結構如何訪(fǎng)問(wèn)外存磁盤(pán)中的數據的情況，下面咱們通過(guò)另外一個(gè)實(shí)例來(lái)對這棵B樹(shù)的插入（insert）,刪除（delete）基本操作進(jìn)行詳細的介紹。

    但在此之前，咱們還得簡(jiǎn)單回顧下一棵m階的B 樹(shù) (m叉樹(shù))的特性，如下：

  1. 樹(shù)中每個(gè)結點(diǎn)含有最多含有m個(gè)孩子，即m滿(mǎn)足：ceil(m/2)<=m<=m。
  2. 除根結點(diǎn)和葉子結點(diǎn)外，其它每個(gè)結點(diǎn)至少有[ceil(m / 2)]個(gè)孩子（其中ceil(x)是一個(gè)取上限的函數）；
  3. 若根結點(diǎn)不是葉子結點(diǎn)，則至少有2個(gè)孩子（特殊情況：沒(méi)有孩子的根結點(diǎn)，即根結點(diǎn)為葉子結點(diǎn)，整棵樹(shù)只有一個(gè)根節點(diǎn)）；
  4. 所有葉子結點(diǎn)都出現在同一層，葉子結點(diǎn)不包含任何關(guān)鍵字信息(可以看做是外部接點(diǎn)或查詢(xún)失敗的接點(diǎn)，實(shí)際上這些結點(diǎn)不存在，指向這些結點(diǎn)的指針都為null)；
  5. 每個(gè)非終端結點(diǎn)中包含有n個(gè)關(guān)鍵字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
           a)   Ki (i=1...n)為關(guān)鍵字，且關(guān)鍵字按順序升序排序K(i-1)< Ki。
           b)   Pi為指向子樹(shù)根的接點(diǎn)，且指針P(i-1)指向子樹(shù)種所有結點(diǎn)的關(guān)鍵字均小于Ki，但都大于K(i-1)。 
           c)   除根結點(diǎn)之外的結點(diǎn)的關(guān)鍵字的個(gè)數n必須滿(mǎn)足： [ceil(m / 2)-1]<= n <= m-1（葉子結點(diǎn)也必須滿(mǎn)足此條關(guān)于關(guān)鍵字數的性質(zhì)，根結點(diǎn)除外）。

    ok，下面咱們以一棵5階（m=5，即除根結點(diǎn)和葉子結點(diǎn)之外的內結點(diǎn)最多5個(gè)孩子，最少3個(gè)孩子）B樹(shù)實(shí)例進(jìn)行講。

備注：

  • 關(guān)鍵字數（2-4個(gè)）針對--非根結點(diǎn)（包括葉子結點(diǎn)在內），孩子數（3-5個(gè)）--針對根結點(diǎn)和葉子結點(diǎn)之外的內結點(diǎn)。當然，根結點(diǎn)是必須至少有2個(gè)孩子的，不然就成直線(xiàn)型搜索樹(shù)了。
  • 我說(shuō)的再明白點(diǎn)就是，一棵5階的B樹(shù)中任何一個(gè)結點(diǎn)的關(guān)鍵字數是1-4，孩子樹(shù)是2-5。同時(shí)，一棵5階的B樹(shù)的最大高度應為log_ceil(m/2)N（下劃線(xiàn)表示以ceil(m/2)為底）。

下圖中關(guān)鍵字為大寫(xiě)字母，順序為字母升序。

結點(diǎn)定義如下：

typedef struct{
   int Count;         // 當前節點(diǎn)中關(guān)鍵元素數目
   ItemType Key[4];   // 存儲關(guān)鍵字元素的數組
   long Branch[5];    // 偽指針數組，(記錄數目)方便判斷合并和分裂的情況
} NodeType;

 

1.1、插入（insert）操作

    插入一個(gè)元素時(shí)，首先在B樹(shù)中是否存在，如果不存在，即在葉子結點(diǎn)處結束，然后在葉子結點(diǎn)中插入該新的元素，注意：

  • 如果葉子結點(diǎn)空間足夠，這里需要向右移動(dòng)該葉子結點(diǎn)中大于新插入關(guān)鍵字的元素，
  • 如果空間滿(mǎn)了以致沒(méi)有足夠的空間去添加新的元素，則將該結點(diǎn)進(jìn)行“分裂”，將一半數量的關(guān)鍵字元素分裂到新的其相鄰右結點(diǎn)中，中間關(guān)鍵字元素上移到父結點(diǎn)中（當然，如果父結點(diǎn)空間滿(mǎn)了，也同樣需要“分裂”操作），而且當結點(diǎn)中關(guān)鍵元素向右移動(dòng)了，相關(guān)的指針也需要向右移。
  • 如果在根結點(diǎn)插入新元素，空間滿(mǎn)了，則進(jìn)行分裂操作，這樣原來(lái)的根結點(diǎn)中的中間關(guān)鍵字元素向上移動(dòng)到新的根結點(diǎn)中，因此導致樹(shù)的高度增加一層。

1、咱們通過(guò)一個(gè)實(shí)例來(lái)逐步講解下。插入以下字符字母到一棵空的B 樹(shù)中（非根結點(diǎn)關(guān)鍵字數小了（小于2個(gè)）就合并，大了（超過(guò)4個(gè)）就分裂）：C N G A H E K Q M F W L T Z D P R X Y S，首先，結點(diǎn)空間足夠，4個(gè)字母插入相同的結點(diǎn)中，如下圖：

 

2、當咱們試著(zhù)插入H時(shí)，結點(diǎn)發(fā)現空間不夠，以致將其分裂成2個(gè)結點(diǎn)，移動(dòng)中間元素G上移到新的根結點(diǎn)中，在實(shí)現過(guò)程中，咱們把A和C留在當前結點(diǎn)中，而H和N放置新的其右鄰居結點(diǎn)中。如下圖：

 

3、當咱們插入E,K,Q時(shí)，不需要任何分裂操作

4、插入M需要一次分裂，注意M恰好是中間關(guān)鍵字元素，以致向上移到父節點(diǎn)中

 

5、插入F,W,L,T不需要任何分裂操作

 

6、插入Z時(shí)，最右的葉子結點(diǎn)空間滿(mǎn)了，需要進(jìn)行分裂操作，中間元素T上移到父節點(diǎn)中，注意通過(guò)上移中間元素，樹(shù)最終還是保持平衡，分裂結果的結點(diǎn)存在2個(gè)關(guān)鍵字元素。

 

7、插入D時(shí)，導致最左邊的葉子結點(diǎn)被分裂，D恰好也是中間元素，上移到父節點(diǎn)中，然后字母P,R,X,Y陸續插入不需要任何分裂操作（別忘了，樹(shù)中至多5個(gè)孩子）。

 

8、最后，當插入S時(shí)，含有N,P,Q,R的結點(diǎn)需要分裂，把中間元素Q上移到父節點(diǎn)中，但是情況來(lái)了，父節點(diǎn)中空間已經(jīng)滿(mǎn)了，所以也要進(jìn)行分裂，將父節點(diǎn)中的中間元素M上移到新形成的根結點(diǎn)中，注意以前在父節點(diǎn)中的第三個(gè)指針在修改后包括D和G節點(diǎn)中。這樣具體插入操作的完成，下面介紹刪除操作，刪除操作相對于插入操作要考慮的情況多點(diǎn)。

 

1.2、刪除(delete)操作

    首先查找B樹(shù)中需刪除的元素,如果該元素在B樹(shù)中存在，則將該元素在其結點(diǎn)中進(jìn)行刪除，如果刪除該元素后，首先判斷該元素是否有左右孩子結點(diǎn)，如果有，則上移孩子結點(diǎn)中的某相近元素到父節點(diǎn)中，然后是移動(dòng)之后的情況；如果沒(méi)有，直接刪除后，移動(dòng)之后的情況。

    刪除元素，移動(dòng)相應元素之后，

  • 如果某結點(diǎn)中元素數目（即關(guān)鍵字數）小于ceil(m/2)-1，則需要看其某相鄰兄弟結點(diǎn)是否豐滿(mǎn)（結點(diǎn)中元素個(gè)數大于ceil(m/2)-1）（還記得第一節中關(guān)于B樹(shù)的第5個(gè)特性中的c點(diǎn)么?： c)除根結點(diǎn)之外的結點(diǎn)（包括葉子結點(diǎn)）的關(guān)鍵字的個(gè)數n必須滿(mǎn)足： （ceil(m / 2)-1）<= n <= m-1。m表示最多含有m個(gè)孩子，n表示關(guān)鍵字數。在本小節中舉的一顆B樹(shù)的示例中，關(guān)鍵字數n滿(mǎn)足：2<=n<=4），
  • 如果豐滿(mǎn)，則向父節點(diǎn)借一個(gè)元素來(lái)滿(mǎn)足條件；
  • 如果其相鄰兄弟都剛脫貧，即借了之后其結點(diǎn)數目小于ceil(m/2)-1，則該結點(diǎn)與其相鄰的某一兄弟結點(diǎn)進(jìn)行“合并”成一個(gè)結點(diǎn)，以此來(lái)滿(mǎn)足條件。

    那咱們通過(guò)下面實(shí)例來(lái)詳細了解吧。

    以上述插入操作構造的一棵5階B樹(shù)（樹(shù)中最多含有m（m=5）個(gè)孩子，因此關(guān)鍵字數最小為ceil(m / 2)-1=2。還是這句話(huà)，關(guān)鍵字數小了（小于2個(gè)）就合并，大了（超過(guò)4個(gè)）就分裂）為例，依次刪除H,T,R,E。

1、首先刪除元素H，當然首先查找H，H在一個(gè)葉子結點(diǎn)中，且該葉子結點(diǎn)元素數目3大于最小元素數目ceil(m/2)-1=2，則操作很簡(jiǎn)單，咱們只需要移動(dòng)K至原來(lái)H的位置，移動(dòng)L至K的位置（也就是結點(diǎn)中刪除元素后面的元素向前移動(dòng)）

 

2、下一步，刪除T,因為T(mén)沒(méi)有在葉子結點(diǎn)中，而是在中間結點(diǎn)中找到，咱們發(fā)現他的繼承者W(字母升序的下個(gè)元素)，將W上移到T的位置，然后將原包含W的孩子結點(diǎn)中的W進(jìn)行刪除，這里恰好刪除W后，該孩子結點(diǎn)中元素個(gè)數大于2，無(wú)需進(jìn)行合并操作。

 

3、下一步刪除R，R在葉子結點(diǎn)中,但是該結點(diǎn)中元素數目為2，刪除導致只有1個(gè)元素，已經(jīng)小于最小元素數目ceil(5/2)-1=2,而由前面我們已經(jīng)知道：如果其某個(gè)相鄰兄弟結點(diǎn)中比較豐滿(mǎn)（元素個(gè)數大于ceil(5/2)-1=2），則可以向父結點(diǎn)借一個(gè)元素，然后將最豐滿(mǎn)的相鄰兄弟結點(diǎn)中上移最后或最前一個(gè)元素到父節點(diǎn)中（有沒(méi)有看到紅黑樹(shù)中左旋操作的影子?），在這個(gè)實(shí)例中，右相鄰兄弟結點(diǎn)中比較豐滿(mǎn)（3個(gè)元素大于2），所以先向父節點(diǎn)借一個(gè)元素W下移到該葉子結點(diǎn)中，代替原來(lái)S的位置，S前移；然后X在相鄰右兄弟結點(diǎn)中上移到父結點(diǎn)中，最后在相鄰右兄弟結點(diǎn)中刪除X，后面元素前移。

 

4、最后一步刪除E， 刪除后會(huì )導致很多問(wèn)題，因為E所在的結點(diǎn)數目剛好達標，剛好滿(mǎn)足最小元素個(gè)數（ceil(5/2)-1=2）,而相鄰的兄弟結點(diǎn)也是同樣的情況，刪除一個(gè)元素都不能滿(mǎn)足條件，所以需要該節點(diǎn)與某相鄰兄弟結點(diǎn)進(jìn)行合并操作；首先移動(dòng)父結點(diǎn)中的元素（該元素在兩個(gè)需要合并的兩個(gè)結點(diǎn)元素之間）下移到其子結點(diǎn)中，然后將這兩個(gè)結點(diǎn)進(jìn)行合并成一個(gè)結點(diǎn)。所以在該實(shí)例中，咱們首先將父節點(diǎn)中的元素D下移到已經(jīng)刪除E而只有F的結點(diǎn)中，然后將含有D和F的結點(diǎn)和含有A,C的相鄰兄弟結點(diǎn)進(jìn)行合并成一個(gè)結點(diǎn)。

 

5、也許你認為這樣刪除操作已經(jīng)結束了，其實(shí)不然，在看看上圖，對于這種特殊情況，你立即會(huì )發(fā)現父節點(diǎn)只包含一個(gè)元素G，沒(méi)達標（因為非根節點(diǎn)包括葉子結點(diǎn)的關(guān)鍵字數n必須滿(mǎn)足于2=<n<=4，而此處的n=1），這是不能夠接受的。如果這個(gè)問(wèn)題結點(diǎn)的相鄰兄弟比較豐滿(mǎn)，則可以向父結點(diǎn)借一個(gè)元素。假設這時(shí)右兄弟結點(diǎn)（含有Q,X）有一個(gè)以上的元素（Q右邊還有元素），然后咱們將M下移到元素很少的子結點(diǎn)中，將Q上移到M的位置，這時(shí)，Q的左子樹(shù)將變成M的右子樹(shù)，也就是含有N，P結點(diǎn)被依附在M的右指針上。所以在這個(gè)實(shí)例中，咱們沒(méi)有辦法去借一個(gè)元素，只能與兄弟結點(diǎn)進(jìn)行合并成一個(gè)結點(diǎn)，而根結點(diǎn)中的唯一元素M下移到子結點(diǎn)，這樣，樹(shù)的高度減少一層。

 

為了進(jìn)一步詳細討論刪除的情況，再舉另外一個(gè)實(shí)例：

這里是一棵不同的5序B樹(shù)，那咱們試著(zhù)刪除C

 

于是將刪除元素C的右子結點(diǎn)中的D元素上移到C的位置，但是出現上移元素后，只有一個(gè)元素的結點(diǎn)的情況。

又因為含有E的結點(diǎn)，其相鄰兄弟結點(diǎn)才剛脫貧（最少元素個(gè)數為2），不可能向父節點(diǎn)借元素，所以只能進(jìn)行合并操作，于是這里將含有A,B的左兄弟結點(diǎn)和含有E的結點(diǎn)進(jìn)行合并成一個(gè)結點(diǎn)。

 

這樣又出現只含有一個(gè)元素F結點(diǎn)的情況，這時(shí)，其相鄰的兄弟結點(diǎn)是豐滿(mǎn)的（元素個(gè)數為3>最小元素個(gè)數2），這樣就可以想父結點(diǎn)借元素了，把父結點(diǎn)中的J下移到該結點(diǎn)中，相應的如果結點(diǎn)中J后有元素則前移，然后相鄰兄弟結點(diǎn)中的第一個(gè)元素（或者最后一個(gè)元素）上移到父節點(diǎn)中，后面的元素（或者前面的元素）前移（或者后移）；注意含有K，L的結點(diǎn)以前依附在M的左邊，現在變?yōu)橐栏皆贘的右邊。這樣每個(gè)結點(diǎn)都滿(mǎn)足B樹(shù)結構性質(zhì)。

 

從以上操作可看出：除根結點(diǎn)之外的結點(diǎn)（包括葉子結點(diǎn)）的關(guān)鍵字的個(gè)數n滿(mǎn)足：（ceil(m / 2)-1）<= n <= m-1，即2<=n<=4。這也佐證了咱們之前的觀(guān)點(diǎn)。刪除操作完。

第二部分、B+ Tree

B+Tree

    B-Tree有許多變種，其中最常見(jiàn)的是B+Tree，例如MySQL就普遍使用B+Tree實(shí)現其索引結構。與B-Tree相比，B+Tree有以下不同點(diǎn)：

  1. 每個(gè)節點(diǎn)的指針上限為2d而不是2d+1。
  2. 內節點(diǎn)不存儲data，只存儲key；葉子節點(diǎn)不存儲指針。

    圖3是一個(gè)簡(jiǎn)單的B+Tree示意。

圖1

    由于并不是所有節點(diǎn)都具有相同的域，因此B+Tree中葉節點(diǎn)和內節點(diǎn)一般大小不同。這點(diǎn)與B-Tree不同，雖然B-Tree中不同節點(diǎn)存放的key和指針可能數量不一致，但是每個(gè)節點(diǎn)的域和上限是一致的，所以在實(shí)現中B-Tree往往對每個(gè)節點(diǎn)申請同等大小的空間。

     一般來(lái)說(shuō)，B+Tree比B-Tree更適合實(shí)現外存儲索引結構，具體原因與外存儲器原理及計算機存取原理有關(guān)，在此不作具體討論。

帶有順序訪(fǎng)問(wèn)指針的B+Tree

    一般在數據庫系統或文件系統中使用的B+Tree結構都在經(jīng)典B+Tree的基礎上進(jìn)行了優(yōu)化，增加了順序訪(fǎng)問(wèn)指針。

                                                                                                      圖4

    如上圖4所示，在B+Tree的每個(gè)葉子節點(diǎn)增加一個(gè)指向相鄰葉子節點(diǎn)的指針，就形成了帶有順序訪(fǎng)問(wèn)指針的B+Tree。做這個(gè)優(yōu)化的目的是為了提高區間訪(fǎng)問(wèn)的性能，例如圖4中如果要查詢(xún)key為從18到49的所有數據記錄，當找到18后，只需順著(zhù)節點(diǎn)和指針順序遍歷就可以一次性訪(fǎng)問(wèn)到所有數據節點(diǎn)，極大提到了區間查詢(xún)效率。（此第二部分參考自：http://www.cnblogs.com/leoo2sk/archive/2011/07/10/mysql-index.html。）

第三部分、B樹(shù)的編碼實(shí)現

    既然明白了B樹(shù)的插入，和刪除操作的原理，接下來(lái)，咱們來(lái)一步一步實(shí)現它。不過(guò)，有一點(diǎn)必須說(shuō)明的是：這個(gè)實(shí)現只是實(shí)現了偶數序order（階)的情況；還有奇數序order（階)的情況沒(méi)有考慮。待日后改進(jìn)。

  • ok，以下是頭文件：
  1. //實(shí)現對order序(階)的B-TREE結構基本操作的封裝。  
  2. //查找：search，插入：insert，刪除：remove。  
  3. //創(chuàng )建：create，銷(xiāo)毀：destory，打?。簆rint。  
  4. #ifndef BTREE_H  
  5. #define BTREE_H  
  6.   
  7. #ifdef __cplusplus  
  8. extern "C" {  
  9. #endif  
  10.   
  11. ////* 定義m序(階)B 樹(shù)的最小度數BTree_D=ceil(m)*/  
  12. /// 在這里定義每個(gè)節點(diǎn)中關(guān)鍵字的最大數目為:2 * BTree_D - 1，即序(階)：2 * BTree_D.  
  13. #define BTree_D        2  
  14. #define ORDER        (BTree_D * 2) //定義為4階B-tree,2-3-4樹(shù)。最簡(jiǎn)單為3階B-tree,2-3樹(shù)。  
  15. //#define ORDER        (BTree_T * 2-1)  //最簡(jiǎn)單為3階B-tree,2-3樹(shù)。  
  16.   
  17.     typedef int KeyType;  
  18.     typedef struct BTNode{  
  19.         int keynum;                        /// 結點(diǎn)中關(guān)鍵字的個(gè)數，keynum <= BTree_N  
  20.         KeyType key[ORDER-1];                /// 關(guān)鍵字向量為key[0..keynum - 1]  
  21.         struct BTNode* child[ORDER];        /// 孩子指針向量為child[0..keynum]  
  22.         bool isLeaf;                    /// 是否是葉子節點(diǎn)的標志  
  23.     }BTNode;  
  24.       
  25.     typedef BTNode* BTree;  ///定義BTree  
  26.       
  27.     ///給定數據集data,創(chuàng )建BTree。  
  28.     void BTree_create(BTree* tree, const KeyType* data, int length);  
  29.   
  30.     ///銷(xiāo)毀BTree，釋放內存空間。  
  31.     void BTree_destroy(BTree* tree);  
  32.       
  33.     ///在BTree中插入關(guān)鍵字key。  
  34.     void BTree_insert(BTree* tree, KeyType key);  
  35.   
  36.     ///在BTree中移除關(guān)鍵字key。  
  37.     void BTree_remove(BTree* tree, KeyType key);  
  38.   
  39.     ///深度遍歷BTree打印各層結點(diǎn)信息。  
  40.     void BTree_print(const BTree tree, int layer=1);  
  41.       
  42.     /// 在BTree中查找關(guān)鍵字 key，  
  43.     /// 成功時(shí)返回找到的節點(diǎn)的地址及 key 在其中的位置 *pos  
  44.     /// 失敗時(shí)返回 NULL 及查找失敗時(shí)掃描到的節點(diǎn)位置 *pos  
  45.     BTNode* BTree_search(const BTree tree, int key, int* pos);  
  46.       
  47. #ifdef __cplusplus  
  48. }  
  49. #endif  
  50.   
  51. #endif  
  • 下面是B樹(shù)的實(shí)現文件：
  1. //實(shí)現對order序(階)的B-TREE結構基本操作的封裝。  
  2. //查找：search，插入：insert，刪除：remove。  
  3. //創(chuàng )建：create，銷(xiāo)毀：destory，打?。簆rint。  
  4. #include <stdlib.h>  
  5. #include <stdio.h>  
  6. #include <assert.h>  
  7. #include "btree.h"  
  8.   
  9. //#define max(a, b) (((a) > (b)) ? (a) : (b))  
  10. #define cmp(a, b) ( ( ((a)-(b)) >= (0) ) ? (1) : (0) ) //比較a，b大小  
  11. #define DEBUG_BTREE  
  12.   
  13.   
  14. // 模擬向磁盤(pán)寫(xiě)入節點(diǎn)  
  15. void disk_write(BTNode* node)  
  16. {  
  17. //打印出結點(diǎn)中的全部元素，方便調試查看keynum之后的元素是否為0(即是否存在垃圾數據)；而不是keynum個(gè)元素。  
  18.     printf("向磁盤(pán)寫(xiě)入節點(diǎn)");  
  19.     for(int i=0;i<ORDER-1;i++){  
  20.         printf("%c",node->key[i]);  
  21.     }  
  22.     printf("\n");  
  23. }  
  24.   
  25. // 模擬從磁盤(pán)讀取節點(diǎn)  
  26. void disk_read(BTNode** node)  
  27. {  
  28. //打印出結點(diǎn)中的全部元素，方便調試查看keynum之后的元素是否為0(即是否存在垃圾數據)；而不是keynum個(gè)元素。  
  29.     printf("向磁盤(pán)讀取節點(diǎn)");  
  30.     for(int i=0;i<ORDER-1;i++){  
  31.         printf("%c",(*node)->key[i]);  
  32.     }  
  33.     printf("\n");  
  34. }  
  35.   
  36. // 按層次打印 B 樹(shù)  
  37. void BTree_print(const BTree tree, int layer)  
  38. {  
  39.     int i;  
  40.     BTNode* node = tree;  
  41.   
  42.     if (node) {  
  43.         printf("第 %d 層， %d node : ", layer, node->keynum);  
  44.   
  45.         //打印出結點(diǎn)中的全部元素，方便調試查看keynum之后的元素是否為0(即是否存在垃圾數據)；而不是keynum個(gè)元素。  
  46.         for (i = 0; i < ORDER-1; ++i) {  
  47.         //for (i = 0; i < node->keynum; ++i) {  
  48.             printf("%c ", node->key[i]);  
  49.         }  
  50.   
  51.         printf("\n");  
  52.   
  53.         ++layer;  
  54.         for (i = 0 ; i <= node->keynum; i++) {  
  55.             if (node->child[i]) {  
  56.                 BTree_print(node->child[i], layer);  
  57.             }  
  58.         }  
  59.     }  
  60.     else {  
  61.         printf("樹(shù)為空。\n");  
  62.     }  
  63. }  
  64.   
  65. // 結點(diǎn)node內對關(guān)鍵字進(jìn)行二分查找。  
  66. int binarySearch(BTNode* node, int low, int high, KeyType Fkey)  
  67. {  
  68.     int mid;  
  69.     while (low<=high)  
  70.     {  
  71.         mid = low + (high-low)/2;  
  72.         if (Fkey<node->key[mid])  
  73.         {  
  74.             high = mid-1;  
  75.         }  
  76.         if (Fkey>node->key[mid])  
  77.         {  
  78.             low = mid+1;  
  79.         }  
  80.         if (Fkey==node->key[mid])  
  81.         {  
  82.             return mid;//返回下標。  
  83.         }  
  84.     }  
  85.     return 0;//未找到返回0.  
  86. }  
  87.   
  88. <span style="color:#660000;"></span>//insert  
  89. /*************************************************************************************** 
  90.    將分裂的結點(diǎn)中的一半元素給新建的結點(diǎn)，并且將分裂結點(diǎn)中的中間關(guān)鍵字元素上移至父節點(diǎn)中。 
  91.    parent 是一個(gè)非滿(mǎn)的父節點(diǎn) 
  92.    node 是 tree 孩子表中下標為 index 的孩子節點(diǎn)，且是滿(mǎn)的，需分裂。 
  93. *******************************************************************/  
  94. void BTree_split_child(BTNode* parent, int index, BTNode* node)  
  95. {  
  96. #ifdef DEBUG_BTREE  
  97.     printf("BTree_split_child!\n");  
  98. #endif  
  99.     assert(parent && node);  
  100.     int i;  
  101.   
  102.     // 創(chuàng )建新節點(diǎn)，存儲 node 中后半部分的數據  
  103.     BTNode* newNode = (BTNode*)calloc(sizeof(BTNode), 1);  
  104.     if (!newNode) {  
  105.         printf("Error! out of memory!\n");  
  106.         return;  
  107.     }  
  108.   
  109.     newNode->isLeaf = node->isLeaf;  
  110.     newNode->keynum = BTree_D - 1;  
  111.   
  112.     // 拷貝 node 后半部分關(guān)鍵字,然后將node后半部分置為0。  
  113.     for (i = 0; i < newNode->keynum; ++i){  
  114.         newNode->key[i] = node->key[BTree_D + i];  
  115.         node->key[BTree_D + i] = 0;  
  116.     }  
  117.   
  118.     // 如果 node 不是葉子節點(diǎn)，拷貝 node 后半部分的指向孩子節點(diǎn)的指針，然后將node后半部分指向孩子節點(diǎn)的指針置為NULL。  
  119.     if (!node->isLeaf) {  
  120.         for (i = 0; i < BTree_D; i++) {  
  121.             newNode->child[i] = node->child[BTree_D + i];  
  122.             node->child[BTree_D + i] = NULL;  
  123.         }  
  124.     }  
  125.   
  126.     // 將 node 分裂出 newNode 之后，里面的數據減半  
  127.     node->keynum = BTree_D - 1;  
  128.   
  129.     // 調整父節點(diǎn)中的指向孩子的指針和關(guān)鍵字元素。分裂時(shí)父節點(diǎn)增加指向孩子的指針和關(guān)鍵元素。  
  130.     for (i = parent->keynum; i > index; --i) {  
  131.         parent->child[i + 1] = parent->child[i];  
  132.     }  
  133.   
  134.     parent->child[index + 1] = newNode;  
  135.   
  136.     for (i = parent->keynum - 1; i >= index; --i) {  
  137.         parent->key[i + 1] = parent->key[i];  
  138.     }  
  139.   
  140.     parent->key[index] = node->key[BTree_D - 1];  
  141.     ++parent->keynum;  
  142.   
  143.     node->key[BTree_D - 1] = 0;  
  144.   
  145.     // 寫(xiě)入磁盤(pán)  
  146.      disk_write(parent);  
  147.      disk_write(newNode);  
  148.      disk_write(node);  
  149. }  
  150.   
  151. void BTree_insert_nonfull(BTNode* node, KeyType key)  
  152. {  
  153.     assert(node);  
  154.   
  155.     int i;  
  156.   
  157.     // 節點(diǎn)是葉子節點(diǎn)，直接插入  
  158.     if (node->isLeaf) {  
  159.         i = node->keynum - 1;  
  160.         while (i >= 0 && key < node->key[i]) {  
  161.             node->key[i + 1] = node->key[i];  
  162.             --i;  
  163.         }  
  164.   
  165.         node->key[i + 1] = key;  
  166.         ++node->keynum;  
  167.   
  168.         // 寫(xiě)入磁盤(pán)  
  169.         disk_write(node);  
  170.     }  
  171.   
  172.     // 節點(diǎn)是內部節點(diǎn)  
  173.     else {  
  174.         /* 查找插入的位置*/  
  175.         i = node->keynum - 1;  
  176.         while (i >= 0 && key < node->key[i]) {  
  177.             --i;  
  178.         }  
  179.   
  180.         ++i;  
  181.   
  182.         // 從磁盤(pán)讀取孩子節點(diǎn)  
  183.         disk_read(&node->child[i]);  
  184.   
  185.         // 如果該孩子節點(diǎn)已滿(mǎn)，分裂調整值  
  186.         if (node->child[i]->keynum == (ORDER-1)) {  
  187.             BTree_split_child(node, i, node->child[i]);  
  188.             // 如果待插入的關(guān)鍵字大于該分裂結點(diǎn)中上移到父節點(diǎn)的關(guān)鍵字，在該關(guān)鍵字的右孩子結點(diǎn)中進(jìn)行插入操作。  
  189.             if (key > node->key[i]) {  
  190.                 ++i;  
  191.             }  
  192.         }  
  193.         BTree_insert_nonfull(node->child[i], key);  
  194.     }  
  195. }  
  196.   
  197. void BTree_insert(BTree* tree, KeyType key)  
  198. {  
  199. #ifdef DEBUG_BTREE  
  200.     printf("BTree_insert:\n");  
  201. #endif  
  202.     BTNode* node;  
  203.     BTNode* root = *tree;  
  204.   
  205.     // 樹(shù)為空  
  206.     if (NULL == root) {  
  207.         root = (BTNode*)calloc(sizeof(BTNode), 1);  
  208.         if (!root) {  
  209.             printf("Error! out of memory!\n");  
  210.             return;  
  211.         }  
  212.         root->isLeaf = true;  
  213.         root->keynum = 1;  
  214.         root->key[0] = key;  
  215.   
  216.         *tree = root;  
  217.   
  218.         // 寫(xiě)入磁盤(pán)  
  219.         disk_write(root);  
  220.   
  221.         return;  
  222.     }  
  223.   
  224.     // 根節點(diǎn)已滿(mǎn)，插入前需要進(jìn)行分裂調整  
  225.     if (root->keynum == (ORDER-1)) {  
  226.         // 產(chǎn)生新節點(diǎn)當作根  
  227.         node = (BTNode*)calloc(sizeof(BTNode), 1);  
  228.         if (!node) {  
  229.             printf("Error! out of memory!\n");  
  230.             return;  
  231.         }  
  232.   
  233.         *tree = node;  
  234.         node->isLeaf = false;  
  235.         node->keynum = 0;  
  236.         node->child[0] = root;  
  237.   
  238.         BTree_split_child(node, 0, root);  
  239.   
  240.         BTree_insert_nonfull(node, key);  
  241.     }  
  242.   
  243.     // 根節點(diǎn)未滿(mǎn)，在當前節點(diǎn)中插入 key  
  244.     else {  
  245.         BTree_insert_nonfull(root, key);  
  246.     }  
  247. }  
  248. <p> </p><p>//remove   
  249. // 對 tree 中的節點(diǎn) node 進(jìn)行合并孩子節點(diǎn)處理.  
  250. // 注意：孩子節點(diǎn)的 keynum 必須均已達到下限，即均等于 BTree_D - 1  
  251. // 將 tree 中索引為 index 的 key 下移至左孩子結點(diǎn)中，  
  252. // 將 node 中索引為 index + 1 的孩子節點(diǎn)合并到索引為 index 的孩子節點(diǎn)中，右孩子合并到左孩子結點(diǎn)中。  
  253. // 并調相關(guān)的 key 和指針。</p>void BTree_merge_child(BTree* tree, BTNode* node, int index)  
  254. {  
  255. #ifdef DEBUG_BTREE  
  256.     printf("BTree_merge_child!\n");  
  257. #endif  
  258.     assert(tree && node && index >= 0 && index < node->keynum);  
  259.   
  260.     int i;  
  261.   
  262.     KeyType key = node->key[index];  
  263.     BTNode* leftChild = node->child[index];  
  264.     BTNode* rightChild = node->child[index + 1];  
  265.   
  266.     assert(leftChild && leftChild->keynum == BTree_D - 1  
  267.         && rightChild && rightChild->keynum == BTree_D - 1);  
  268.   
  269.     // 將 node中關(guān)鍵字下標為index 的 key 下移至左孩子結點(diǎn)中，該key所對應的右孩子結點(diǎn)指向node的右孩子結點(diǎn)中的第一個(gè)孩子。  
  270.     leftChild->key[leftChild->keynum] = key;  
  271.     leftChild->child[leftChild->keynum + 1] = rightChild->child[0];  
  272.     ++leftChild->keynum;  
  273.   
  274.     // 右孩子的元素合并到左孩子結點(diǎn)中。  
  275.     for (i = 0; i < rightChild->keynum; ++i) {  
  276.         leftChild->key[leftChild->keynum] = rightChild->key[i];  
  277.         leftChild->child[leftChild->keynum + 1] = rightChild->child[i + 1];  
  278.         ++leftChild->keynum;  
  279.     }  
  280.   
  281.     // 在 node 中下移的 key后面的元素前移  
  282.     for (i = index; i < node->keynum - 1; ++i) {  
  283.         node->key[i] = node->key[i + 1];  
  284.         node->child[i + 1] = node->child[i + 2];  
  285.     }  
  286.     node->key[node->keynum - 1] = 0;  
  287.     node->child[node->keynum] = NULL;  
  288.     --node->keynum;  
  289.   
  290.     // 如果根節點(diǎn)沒(méi)有 key 了，并將根節點(diǎn)調整為合并后的左孩子節點(diǎn)；然后刪除釋放空間。  
  291.     if (node->keynum == 0) {  
  292.         if (*tree == node) {  
  293.             *tree = leftChild;  
  294.         }  
  295.   
  296.         free(node);  
  297.         node = NULL;  
  298.     }  
  299.   
  300.     free(rightChild);  
  301.     rightChild = NULL;  
  302. }  
  303.   
  304. void BTree_recursive_remove(BTree* tree, KeyType key)  
  305. {  
  306.     // B-數的保持條件之一：  
  307.     // 非根節點(diǎn)的內部節點(diǎn)的關(guān)鍵字數目不能少于 BTree_D - 1  
  308.   
  309.     int i, j, index;  
  310.     BTNode *root = *tree;  
  311.     BTNode *node = root;  
  312.   
  313.     if (!root) {  
  314.         printf("Failed to remove %c, it is not in the tree!\n", key);  
  315.         return;  
  316.     }  
  317.   
  318.     // 結點(diǎn)中找key。  
  319.     index = 0;  
  320.     while (index < node->keynum && key > node->key[index]) {  
  321.         ++index;  
  322.     }  
  323.   
  324. /*======================含有key的當前結點(diǎn)時(shí)的情況==================== 
  325. node: 
  326. index of Key:            i-1  i  i+1 
  327.                         +---+---+---+---+ 
  328.                           *  key   * 
  329.                     +---+---+---+---+---+ 
  330.                            /     \ 
  331. index of Child:           i      i+1 
  332.                          /         \ 
  333.                     +---+---+      +---+---+ 
  334.                       *   *           *   *    
  335.                 +---+---+---+  +---+---+---+ 
  336.                     leftChild     rightChild 
  337. ============================================================*/  
  338.     /*一、結點(diǎn)中找到了關(guān)鍵字key的情況.*/  
  339.     BTNode *leftChild, *rightChild;  
  340.     KeyType leftKey, rightKey;  
  341.     if (index < node->keynum && node->key[index] == key) {  
  342.         /* 1，所在節點(diǎn)是葉子節點(diǎn)，直接刪除*/  
  343.         if (node->isLeaf) {  
  344.             for (i = index; i < node->keynum-1; ++i) {  
  345.                 node->key[i] = node->key[i + 1];  
  346.                 //node->child[i + 1] = node->child[i + 2];葉子節點(diǎn)的孩子結點(diǎn)為空，無(wú)需移動(dòng)處理。  
  347.             }  
  348.             node->key[node->keynum-1] = 0;  
  349.             //node->child[node->keynum] = NULL;  
  350.             --node->keynum;  
  351.   
  352.             if (node->keynum == 0) {  
  353.                 assert(node == *tree);  
  354.                 free(node);  
  355.                 *tree = NULL;  
  356.             }  
  357.   
  358.             return;  
  359.         }  
  360.         /*2.選擇脫貧致富的孩子結點(diǎn)。*/  
  361.         // 2a，選擇相對富有的左孩子結點(diǎn)。  
  362.         // 如果位于 key 前的左孩子結點(diǎn)的 key 數目 >= BTree_D，  
  363.         // 在其中找 key 的左孩子結點(diǎn)的最后一個(gè)元素上移至父節點(diǎn)key的位置。  
  364.         // 然后在左孩子節點(diǎn)中遞歸刪除元素leftKey。  
  365.         else if (node->child[index]->keynum >= BTree_D) {  
  366.             leftChild = node->child[index];  
  367.             leftKey = leftChild->key[leftChild->keynum - 1];  
  368.             node->key[index] = leftKey;  
  369.   
  370.             BTree_recursive_remove(&leftChild, leftKey);  
  371.         }  
  372.         // 2b，選擇相對富有的右孩子結點(diǎn)。  
  373.         // 如果位于 key 后的右孩子結點(diǎn)的 key 數目 >= BTree_D，  
  374.         // 在其中找 key 的右孩子結點(diǎn)的第一個(gè)元素上移至父節點(diǎn)key的位置  
  375.         // 然后在右孩子節點(diǎn)中遞歸刪除元素rightKey。  
  376.         else if (node->child[index + 1]->keynum >= BTree_D) {  
  377.             rightChild = node->child[index + 1];  
  378.             rightKey = rightChild->key[0];  
  379.             node->key[index] = rightKey;  
  380.   
  381.             BTree_recursive_remove(&rightChild, rightKey);  
  382.         }  
  383.         /*左右孩子結點(diǎn)都剛脫貧。刪除前需要孩子結點(diǎn)的合并操作*/  
  384.         // 2c，左右孩子結點(diǎn)只包含 BTree_D - 1 個(gè)節點(diǎn)，  
  385.         // 合并是將 key 下移至左孩子節點(diǎn)，并將右孩子節點(diǎn)合并到左孩子節點(diǎn)中，  
  386.         // 刪除右孩子節點(diǎn)，在父節點(diǎn)node中移除 key 和指向右孩子節點(diǎn)的指針，  
  387.         // 然后在合并了的左孩子節點(diǎn)中遞歸刪除元素key。  
  388.         else if (node->child[index]->keynum == BTree_D - 1  
  389.             && node->child[index + 1]->keynum == BTree_D - 1){  
  390.             leftChild = node->child[index];  
  391.   
  392.             BTree_merge_child(tree, node, index);  
  393.   
  394.             // 在合并了的左孩子節點(diǎn)中遞歸刪除 key  
  395.             BTree_recursive_remove(&leftChild, key);  
  396.         }  
  397.     }  
  398.   
  399. /*======================未含有key的當前結點(diǎn)時(shí)的情況==================== 
  400. node: 
  401. index of Key:            i-1  i  i+1 
  402.                         +---+---+---+---+ 
  403.                           *  keyi * 
  404.                     +---+---+---+---+---+ 
  405.                        /    |    \ 
  406. index of Child:      i-1    i     i+1 
  407.                      /      |       \ 
  408.             +---+---+   +---+---+      +---+---+ 
  409.              *   *        *   *          *   *    
  410.         +---+---+---+   +---+---+---+  +---+---+---+ 
  411.         leftSibling       Child        rightSibling  
  412. ============================================================*/  
  413.     /*二、結點(diǎn)中未找到了關(guān)鍵字key的情況.*/  
  414.     else {  
  415.         BTNode *leftSibling, *rightSibling, *child;  
  416.         // 3. key 不在內節點(diǎn) node 中，則應當在某個(gè)包含 key 的子節點(diǎn)中。  
  417.         //  key < node->key[index], 所以 key 應當在孩子節點(diǎn) node->child[index] 中  
  418.         child = node->child[index];  
  419.         if (!child) {  
  420.             printf("Failed to remove %c, it is not in the tree!\n", key);  
  421.             return;  
  422.         }  
  423.         /*所需查找的該孩子結點(diǎn)剛脫貧的情況*/  
  424.         if (child->keynum == BTree_D - 1) {  
  425.             leftSibling = NULL;  
  426.             rightSibling = NULL;  
  427.   
  428.             if (index - 1 >= 0) {  
  429.                 leftSibling = node->child[index - 1];  
  430.             }  
  431.   
  432.             if (index + 1 <= node->keynum) {  
  433.                 rightSibling = node->child[index + 1];  
  434.             }  
  435.             /*選擇致富的相鄰兄弟結點(diǎn)。*/  
  436.             // 3a，如果所在孩子節點(diǎn)相鄰的兄弟節點(diǎn)中有節點(diǎn)至少包含 BTree_D 個(gè)關(guān)鍵字  
  437.             // 將 node 的一個(gè)關(guān)鍵字key[index]下移到 child 中，將相對富有的相鄰兄弟節點(diǎn)中一個(gè)關(guān)鍵字上移到  
  438.             // node 中，然后在 child 孩子節點(diǎn)中遞歸刪除 key。  
  439.             if ((leftSibling && leftSibling->keynum >= BTree_D)  
  440.                 || (rightSibling && rightSibling->keynum >= BTree_D)) {  
  441.                 int richR = 0;  
  442.                 if(rightSibling) richR = 1;  
  443.                 if(leftSibling && rightSibling) {  
  444.                     richR = cmp(rightSibling->keynum,leftSibling->keynum);  
  445.                 }  
  446.                 if (rightSibling && rightSibling->keynum >= BTree_D && richR) {  
  447.         //相鄰右兄弟相對富有，則該孩子先向父節點(diǎn)借一個(gè)元素，右兄弟中的第一個(gè)元素上移至父節點(diǎn)所借位置，并進(jìn)行相應調整。  
  448.                     child->key[child->keynum] = node->key[index];  
  449.                     child->child[child->keynum + 1] = rightSibling->child[0];  
  450.                     ++child->keynum;  
  451.   
  452.                     node->key[index] = rightSibling->key[0];  
  453.   
  454.                     for (j = 0; j < rightSibling->keynum - 1; ++j) {//元素前移  
  455.                         rightSibling->key[j] = rightSibling->key[j + 1];  
  456.                         rightSibling->child[j] = rightSibling->child[j + 1];  
  457.                     }  
  458.                     rightSibling->key[rightSibling->keynum-1] = 0;  
  459.                     rightSibling->child[rightSibling->keynum-1] = rightSibling->child[rightSibling->keynum];  
  460.                     rightSibling->child[rightSibling->keynum] = NULL;  
  461.                     --rightSibling->keynum;  
  462.                 }  
  463.                 else {//相鄰左兄弟相對富有，則該孩子向父節點(diǎn)借一個(gè)元素，左兄弟中的最后元素上移至父節點(diǎn)所借位置，并進(jìn)行相應調整。  
  464.                     for (j = child->keynum; j > 0; --j) {//元素后移  
  465.                         child->key[j] = child->key[j - 1];  
  466.                         child->child[j + 1] = child->child[j];  
  467.                     }  
  468.                     child->child[1] = child->child[0];  
  469.                     child->child[0] = leftSibling->child[leftSibling->keynum];  
  470.                     child->key[0] = node->key[index - 1];  
  471.                     ++child->keynum;  
  472.   
  473.                     node->key[index - 1] = leftSibling->key[leftSibling->keynum - 1];  
  474.   
  475.                     leftSibling->key[leftSibling->keynum - 1] = 0;  
  476.                     leftSibling->child[leftSibling->keynum] = NULL;  
  477.   
  478.                     --leftSibling->keynum;  
  479.                 }  
  480.             }  
  481.             /*相鄰兄弟結點(diǎn)都剛脫貧。刪除前需要兄弟結點(diǎn)的合并操作,*/  
  482.             // 3b, 如果所在孩子節點(diǎn)相鄰的兄弟節點(diǎn)都只包含 BTree_D - 1 個(gè)關(guān)鍵字，  
  483.             // 將 child 與其一相鄰節點(diǎn)合并，并將 node 中的一個(gè)關(guān)鍵字下降到合并節點(diǎn)中，  
  484.             // 再在 node 中刪除那個(gè)關(guān)鍵字和相關(guān)指針，若 node 的 key 為空，刪之，并調整根為合并結點(diǎn)。  
  485.             // 最后，在相關(guān)孩子節點(diǎn)child中遞歸刪除 key。  
  486.             else if ((!leftSibling || (leftSibling && leftSibling->keynum == BTree_D - 1))  
  487.                 && (!rightSibling || (rightSibling && rightSibling->keynum == BTree_D - 1))) {  
  488.                 if (leftSibling && leftSibling->keynum == BTree_D - 1) {  
  489.   
  490.                     BTree_merge_child(tree, node, index - 1);//node中的右孩子元素合并到左孩子中。  
  491.   
  492.                     child = leftSibling;  
  493.                 }  
  494.   
  495.                 else if (rightSibling && rightSibling->keynum == BTree_D - 1) {  
  496.   
  497.                     BTree_merge_child(tree, node, index);//node中的右孩子元素合并到左孩子中。  
  498.                 }  
  499.             }  
  500.         }  
  501.   
  502.         BTree_recursive_remove(&child, key);//調整后，在key所在孩子結點(diǎn)中繼續遞歸刪除key。  
  503.     }  
  504. }  
  505.   
  506. void BTree_remove(BTree* tree, KeyType key)  
  507. {  
  508. #ifdef DEBUG_BTREE  
  509.     printf("BTree_remove:\n");  
  510. #endif  
  511.     if (*tree==NULL)  
  512.     {     
  513.         printf("BTree is NULL!\n");  
  514.         return;  
  515.     }  
  516.   
  517.     BTree_recursive_remove(tree, key);  
  518. }  
  519.   
  520. //=====================================search====================================  
  521.   
  522. BTNode* BTree_recursive_search(const BTree tree, KeyType key, int* pos)  
  523. {  
  524.     int i = 0;  
  525.   
  526.     while (i < tree->keynum && key > tree->key[i]) {  
  527.         ++i;  
  528.     }  
  529.   
  530.     // Find the key.  
  531.     if (i < tree->keynum && tree->key[i] == key) {  
  532.         *pos = i;  
  533.         return tree;  
  534.     }  
  535.   
  536.     // tree 為葉子節點(diǎn)，找不到 key，查找失敗返回  
  537.     if (tree->isLeaf) {  
  538.         return NULL;  
  539.     }  
  540.   
  541.     // 節點(diǎn)內查找失敗，但 tree->key[i - 1]< key < tree->key[i]，  
  542.     // 下一個(gè)查找的結點(diǎn)應為 child[i]  
  543.   
  544.     // 從磁盤(pán)讀取第 i 個(gè)孩子的數據  
  545.     disk_read(&tree->child[i]);  
  546.   
  547.     // 遞歸地繼續查找于樹(shù) tree->child[i]  
  548.     return BTree_recursive_search(tree->child[i], key, pos);  
  549. }  
  550.   
  551. BTNode* BTree_search(const BTree tree, KeyType key, int* pos)  
  552. {  
  553. #ifdef DEBUG_BTREE  
  554.     printf("BTree_search:\n");  
  555. #endif  
  556.     if (!tree) {  
  557.         printf("BTree is NULL!\n");  
  558.         return NULL;  
  559.     }  
  560.     *pos = -1;  
  561.     return BTree_recursive_search(tree,key,pos);  
  562. }  
  563.   
  564. //===============================create===============================  
  565. void BTree_create(BTree* tree, const KeyType* data, int length)  
  566. {  
  567.     assert(tree);  
  568.   
  569.     int i;  
  570.   
  571. #ifdef DEBUG_BTREE  
  572.     printf("\n 開(kāi)始創(chuàng )建 B-樹(shù)，關(guān)鍵字為:\n");  
  573.     for (i = 0; i < length; i++) {  
  574.         printf(" %c ", data[i]);  
  575.     }  
  576.     printf("\n");  
  577. #endif  
  578.   
  579.     for (i = 0; i < length; i++) {  
  580. #ifdef DEBUG_BTREE  
  581.         printf("\n插入關(guān)鍵字 %c:\n", data[i]);  
  582. #endif  
  583.         int pos = -1;  
  584.         BTree_search(*tree,data[i],&pos);//樹(shù)的遞歸搜索。  
  585.         if (pos!=-1)  
  586.         {  
  587.             printf("this key %c is in the B-tree,not to insert.\n",data[i]);  
  588.         }else{  
  589.             BTree_insert(tree, data[i]);//插入元素到BTree中。  
  590.         }  
  591.   
  592. #ifdef DEBUG_BTREE  
  593.         BTree_print(*tree);//樹(shù)的深度遍歷。  
  594. #endif  
  595.     }  
  596.   
  597.     printf("\n");  
  598. }  
  599. //===============================destroy===============================  
  600. void BTree_destroy(BTree* tree)  
  601. {  
  602.     int i;  
  603.     BTNode* node = *tree;  
  604.   
  605.     if (node) {  
  606.         for (i = 0; i <= node->keynum; i++) {  
  607.             BTree_destroy(&node->child[i]);  
  608.         }  
  609.   
  610.         free(node);  
  611.     }  
  612.   
  613.     *tree = NULL;  
  614. }  
  • 最后，給出測試文件：
  1. //測試order序(階)的B-TREE結構基本操作。  
  2. //查找：search，插入：insert，刪除：remove。  
  3. //創(chuàng )建：create，銷(xiāo)毀：destory，打?。簆rint。  
  4.   
  5. #include <stdio.h>  
  6. #include "btree.h"  
  7.   
  8. void test_BTree_search(BTree tree, KeyType key)  
  9. {  
  10.     int pos = -1;  
  11.     BTNode*    node = BTree_search(tree, key, &pos);  
  12.     if (node) {  
  13.         printf("在%s節點(diǎn)（包含 %d 個(gè)關(guān)鍵字）中找到關(guān)鍵字 %c，其索引為 %d\n",  
  14.             node->isLeaf ? "葉子" : "非葉子",  
  15.             node->keynum, key, pos);  
  16.     }  
  17.     else {  
  18.         printf("在樹(shù)中找不到關(guān)鍵字 %c\n", key);  
  19.     }  
  20. }  
  21.   
  22. void test_BTree_remove(BTree* tree, KeyType key)  
  23. {  
  24.     printf("\n移除關(guān)鍵字 %c \n", key);  
  25.     BTree_remove(tree, key);  
  26.     BTree_print(*tree);  
  27.     printf("\n");  
  28. }  
  29.   
  30. void test_btree()  
  31. {  
  32.   
  33.     KeyType array[] = {  
  34.         'G','G', 'M', 'P', 'X', 'A', 'C', 'D', 'E', 'J', 'K',  
  35.         'N', 'O', 'R', 'S', 'T', 'U', 'V', 'Y', 'Z', 'F', 'X'  
  36.     };  
  37.     const int length = sizeof(array)/sizeof(KeyType);  
  38.     BTree tree = NULL;  
  39.     BTNode* node = NULL;  
  40.     int pos = -1;  
  41.     KeyType key1 = 'R';        // in the tree.  
  42.     KeyType key2 = 'B';        // not in the tree.  
  43.   
  44.     // 創(chuàng )建  
  45.     BTree_create(&tree, array, length);  
  46.   
  47.     printf("\n=== 創(chuàng )建 B- 樹(shù) ===\n");  
  48.     BTree_print(tree);  
  49.     printf("\n");  
  50.   
  51.     // 查找  
  52.     test_BTree_search(tree, key1);  
  53.     printf("\n");  
  54.     test_BTree_search(tree, key2);  
  55.   
  56.     // 移除不在B樹(shù)中的元素  
  57.     test_BTree_remove(&tree, key2);  
  58.     printf("\n");  
  59.   
  60.     // 插入關(guān)鍵字  
  61.     printf("\n插入關(guān)鍵字 %c \n", key2);  
  62.     BTree_insert(&tree, key2);  
  63.     BTree_print(tree);  
  64.     printf("\n");  
  65.   
  66.     test_BTree_search(tree, key2);  
  67.   
  68.     // 移除關(guān)鍵字  
  69.     test_BTree_remove(&tree, key2);  
  70.     test_BTree_search(tree, key2);  
  71.   
  72.     key2 = 'M';  
  73.     test_BTree_remove(&tree, key2);  
  74.     test_BTree_search(tree, key2);  
  75.   
  76.     key2 = 'E';  
  77.     test_BTree_remove(&tree, key2);  
  78.     test_BTree_search(tree, key2);  
  79.   
  80.     key2 = 'G';  
  81.     test_BTree_remove(&tree, key2);  
  82.     test_BTree_search(tree, key2);  
  83.   
  84.     key2 = 'A';  
  85.     test_BTree_remove(&tree, key2);  
  86.     test_BTree_search(tree, key2);  
  87.   
  88.     key2 = 'D';  
  89.     test_BTree_remove(&tree, key2);  
  90.     test_BTree_search(tree, key2);  
  91.   
  92.     key2 = 'K';  
  93.     test_BTree_remove(&tree, key2);  
  94.     test_BTree_search(tree, key2);  
  95.   
  96.     key2 = 'P';  
  97.     test_BTree_remove(&tree, key2);  
  98.     test_BTree_search(tree, key2);  
  99.   
  100.     key2 = 'J';  
  101.     test_BTree_remove(&tree, key2);  
  102.     test_BTree_search(tree, key2);  
  103.   
  104.     key2 = 'C';  
  105.     test_BTree_remove(&tree, key2);  
  106.     test_BTree_search(tree, key2);  
  107.   
  108.     key2 = 'X';  
  109.     test_BTree_remove(&tree, key2);  
  110.     test_BTree_search(tree, key2);  
  111.   
  112.     key2 = 'O';  
  113.     test_BTree_remove(&tree, key2);  
  114.     test_BTree_search(tree, key2);  
  115.   
  116.     key2 = 'V';  
  117.     test_BTree_remove(&tree, key2);  
  118.     test_BTree_search(tree, key2);  
  119.   
  120.     key2 = 'R';  
  121.     test_BTree_remove(&tree, key2);  
  122.     test_BTree_search(tree, key2);  
  123.   
  124.     key2 = 'U';  
  125.     test_BTree_remove(&tree, key2);  
  126.     test_BTree_search(tree, key2);  
  127.   
  128.     key2 = 'T';  
  129.     test_BTree_remove(&tree, key2);  
  130.     test_BTree_search(tree, key2);  
  131.   
  132.     key2 = 'N';  
  133.     test_BTree_remove(&tree, key2);  
  134.     test_BTree_search(tree, key2);  
  135.     key2 = 'S';  
  136.     test_BTree_remove(&tree, key2);  
  137.     test_BTree_search(tree, key2);  
  138.     key2 = 'Y';  
  139.     test_BTree_remove(&tree, key2);  
  140.     test_BTree_search(tree, key2);  
  141.     key2 = 'F';  
  142.     test_BTree_remove(&tree, key2);  
  143.     test_BTree_search(tree, key2);  
  144.     key2 = 'Z';  
  145.     test_BTree_remove(&tree, key2);  
  146.     test_BTree_search(tree, key2);  
  147.   
  148.     // 銷(xiāo)毀  
  149.     BTree_destroy(&tree);  
  150. }  
  151.   
  152. int main()  
  153. {  
  154.     test_btree();  
  155.   
  156.     return 0;  
  157. }  

    運行結果部分截圖如下：



參考：

  1. http://www.cppblog.com/converse/archive/2009/10/13/98521.html；
  2. 此外，這里有一份google關(guān)于B樹(shù)的C++實(shí)現：https://code.google.com/p/cpp-btree/downloads/detail?name=cpp-btree-1.0.1.tar.gz。

聯(lián)系作者：

    若有任何問(wèn)題，歡迎隨時(shí)不吝指正?；蛘呗?lián)系我們：

后記：

    本blog日后會(huì )更多的關(guān)注數據結構與算法之外的東西，如分布式架構，海量數據處理，搜索引擎相關(guān)。畢竟，算法之外的東西，如瀚海般無(wú)止境，要學(xué)的東西，還有很多。

    若轉載，請注明出處，謝謝。完。二零一一年八月三十一日。

本站僅提供存儲服務(wù)，所有內容均由用戶(hù)發(fā)布，如發(fā)現有害或侵權內容，請點(diǎn)擊舉報。
打開(kāi)APP，閱讀全文并永久保存 查看更多類(lèi)似文章
猜你喜歡
類(lèi)似文章
6天通吃樹(shù)結構－Ｔreap數
精解四大集合框架：Map核心知識總結
最近最少使用（LRU）緩存淘汰算法
數據結構與算法15—二叉排序(查找)樹(shù)
nginx的數據結構(4) 基樹(shù)ngx
c語(yǔ)言實(shí)現二叉查找樹(shù)實(shí)例方法
更多類(lèi)似文章 >>
生活服務(wù)
分享 收藏 導長(cháng)圖 關(guān)注 下載文章
綁定賬號成功
后續可登錄賬號暢享VIP特權！
如果VIP功能使用有故障，
可點(diǎn)擊這里聯(lián)系客服！

聯(lián)系客服

欧美性猛交XXXX免费看蜜桃,成人网18免费韩国,亚洲国产成人精品区综合,欧美日韩一区二区三区高清不卡,亚洲综合一区二区精品久久