數(shù)據(jù)結(jié)構(gòu)講義九：二叉排序樹

1、動(dòng)態(tài)查找 二叉排序樹二叉排序樹 平衡二叉樹平衡二叉樹 B-樹（樹（B+樹）樹） 鍵樹鍵樹二叉排序樹二叉排序樹 二叉排序樹二叉排序樹：或是一棵空二叉樹，或是一棵具有下或是一棵空二叉樹，或是一棵具有下列性質(zhì)的二叉樹：若左子樹非空，則左子樹上列性質(zhì)的二叉樹：若左子樹非空，則左子樹上所有所有結(jié)點(diǎn)的值均小于結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若右子樹非空，則右根結(jié)點(diǎn)的值；若右子樹非空，則右子樹上子樹上所有結(jié)點(diǎn)的值均大于所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；并且其左、根結(jié)點(diǎn)的值；并且其左、右子樹均是二叉排序樹。右子樹均是二叉排序樹。類型定義為：類型定義為：typedef struct BSTNode intkey; 關(guān)鍵字

2、域關(guān)鍵字域 其它數(shù)據(jù)域其它數(shù)據(jù)域 struct BSTNode *lchild,*rchild;左、右孩子指針左、右孩子指針 BSTNode,*BSTree; 二叉排序樹示例30125332394187189查找查找7171、5 5 二叉排序樹的查找算法假定二叉排序樹的根結(jié)點(diǎn)指針為 root ，給定的關(guān)鍵字值為 K ，則查找算法可描述為： 置初值： q root ； 如果 K q key ，則查找成功，算法結(jié)束； 否則，如果 K q key ，而且 q 的左子樹非空，則將 q 的左子樹根送 q ，轉(zhuǎn)步驟；否則，查找失敗，結(jié)束算法； 否則，如果 K q key ，而且 q 的右子樹非空，則將 q

3、 的右子樹根送 q ，轉(zhuǎn)步驟；否則，查找失敗，算法結(jié)束。int Bstree:Search(KeyType K) int flag=0; BstNode*q=root; while(q!=NULL)&(flag=0) if(q-key=K) cout查找成功，找到：查找成功，找到：keyendl; flag=1; else if(Kkey)q=q-lch; elseq=q-rch; if(flag=0)coutkey!=k) if(kkey) p=p-lchild; else p=p-rchild; return p;/SearchBST2 二叉排序樹上結(jié)點(diǎn)的插入 步驟步驟： （1）若

4、二叉排序樹是空樹，則）若二叉排序樹是空樹，則k成為二叉排序成為二叉排序樹的根；樹的根；（2 2）若二叉排序樹非空，則將）若二叉排序樹非空，則將k與二叉排序樹的與二叉排序樹的根進(jìn)行比較，如果根進(jìn)行比較，如果k的值等于根結(jié)點(diǎn)的值，則停的值等于根結(jié)點(diǎn)的值，則停止插入；如果止插入；如果k的值小于根結(jié)點(diǎn)的值，則將的值小于根結(jié)點(diǎn)的值，則將k插入插入左子樹；如果左子樹；如果k的值大于根結(jié)點(diǎn)的值，則將的值大于根結(jié)點(diǎn)的值，則將k插入插入右子樹。右子樹。 插入算法void InsertBST(BSTree t,int k)/若二叉排序樹若二叉排序樹t中沒有關(guān)鍵字中沒有關(guān)鍵字k，則插入，否則直接返回，則插入，否則直

5、接返回 p=t; /p的初值指向根結(jié)點(diǎn)的初值指向根結(jié)點(diǎn) while(p) /查找插入位置查找插入位置 if (p-key=k) return; /已有已有k，無需插入，無需插入 f=p; /f保存當(dāng)前查找的結(jié)點(diǎn)保存當(dāng)前查找的結(jié)點(diǎn) p=(kkey)?p-lchild:p-rchild; /若若kkey，在左子樹上查找，否則在右子樹上查找，在左子樹上查找，否則在右子樹上查找 p=(BSTree)malloc(sizeof(BSTNode); p-key=k; p-lchild=p-rchild=NULL; if(t=NULL) t=p; else if (kkey) f-lchild=p; els

6、e f-rchild=p;/InsertBST 123532264520(g)二叉排序樹的生成 (b)32(c)3226 (d)322645(a)32264535 (e)3226451235 (f)設(shè)序列為設(shè)序列為(32,26,45,35,12,20)(32,26,45,35,12,20)記錄的關(guān)鍵碼序列為：63，90，70，55，67，42，98，83，則構(gòu)造一棵二叉排序樹的過程如下：636390706390557063906755706390426755706390984267557063908398426755706390二叉排序樹上結(jié)點(diǎn)的刪除 假設(shè)要?jiǎng)h除的結(jié)點(diǎn)為假設(shè)要?jiǎng)h除的結(jié)點(diǎn)為*p，

7、結(jié)點(diǎn)，結(jié)點(diǎn)*p的雙親結(jié)的雙親結(jié)點(diǎn)為點(diǎn)為*f，并假設(shè)結(jié)點(diǎn)，并假設(shè)結(jié)點(diǎn)*p是結(jié)點(diǎn)是結(jié)點(diǎn)*f的左孩子的左孩子(右孩右孩子的情況類似子的情況類似)。下面分三種情況討論：。下面分三種情況討論：若若*p為葉子結(jié)點(diǎn)，則可直接將其刪除：為葉子結(jié)點(diǎn)，則可直接將其刪除：f-1childNULL; free(p)；若若*p結(jié)點(diǎn)只有左子樹，或只有右子樹，則可將結(jié)點(diǎn)只有左子樹，或只有右子樹，則可將*p的左子的左子樹或右子樹直接改為其雙親結(jié)點(diǎn)樹或右子樹直接改為其雙親結(jié)點(diǎn)*f的左子樹，即：的左子樹，即：f-1child=p-1child(或或f-1child=p-rchild); free(p)；FP*f*pP1FP1*f

8、FP*f*pPrFPr*f若若*p既有左子樹，又有右子樹。則：既有左子樹，又有右子樹。則： 令令*p結(jié)點(diǎn)的結(jié)點(diǎn)的直接前驅(qū)直接前驅(qū)（或直接后繼）代替（或直接后繼）代替*p，然后再從二叉排序樹中，然后再從二叉排序樹中刪除它的直接前驅(qū)（或直接后繼）。當(dāng)以直接前驅(qū)刪除它的直接前驅(qū)（或直接后繼）。當(dāng)以直接前驅(qū)*s代替代替*p時(shí)，由于時(shí)，由于*s只只有左子樹有左子樹SL，則在刪去，則在刪去*s之后，只要令之后，只要令SL為為*s的雙親的雙親*r的右子樹即可的右子樹即可RQ QqFSFRPRpQ QLrRLSLSRQ QqFPFRPRpQ QLrsRLSL二叉排序樹上刪除10或40或45或555845439

9、832405570639010void Delete(BSTree bst, keytype X) /在二叉排序樹在二叉排序樹bst上，刪除其關(guān)鍵字為上，刪除其關(guān)鍵字為X的結(jié)點(diǎn)。的結(jié)點(diǎn)。 BSTree f,p=bst; while (p & p-key!=X) /查找值為查找值為X的結(jié)點(diǎn)的結(jié)點(diǎn) if (p-keyX) f=p; p=p-lchild; else f=p; p=p-rchild; if (p=null) printf(“無關(guān)鍵字為無關(guān)鍵字為X的結(jié)點(diǎn)的結(jié)點(diǎn)n”); exit(0); if p-lchild=null /被刪結(jié)點(diǎn)無左子樹被刪結(jié)點(diǎn)無左子樹 if (f-lchil

10、d=p) f-lchild=p-rchild;/將被刪結(jié)點(diǎn)的右子樹接到其雙親將被刪結(jié)點(diǎn)的右子樹接到其雙親上上 else f-rchild=p-rchild; else /被刪結(jié)點(diǎn)有左子樹被刪結(jié)點(diǎn)有左子樹 q=p; s=p-lchild; /s指向被刪結(jié)點(diǎn)左子樹的根指向被刪結(jié)點(diǎn)左子樹的根 while (s-rchild !=null) /查左子樹中最右下的結(jié)點(diǎn)（中序最后結(jié)點(diǎn)）查左子樹中最右下的結(jié)點(diǎn)（中序最后結(jié)點(diǎn)） q=s; s=s-rchild; p-key=s-key; /結(jié)點(diǎn)值用其左子樹最右下的結(jié)點(diǎn)的值代替結(jié)點(diǎn)值用其左子樹最右下的結(jié)點(diǎn)的值代替 if (q=p) p-lchild=s-lchi

11、ld;/被刪結(jié)點(diǎn)左子樹的根結(jié)點(diǎn)無右子女被刪結(jié)點(diǎn)左子樹的根結(jié)點(diǎn)無右子女 else q-rchild=s-lchild; /s是被刪結(jié)點(diǎn)左子樹中序最后一個(gè)結(jié)是被刪結(jié)點(diǎn)左子樹中序最后一個(gè)結(jié)點(diǎn)點(diǎn) free(s); /算法結(jié)束算法結(jié)束 最佳二叉排序樹 定義定義 ：平均查找長度最小的二叉排序樹。平均查找長度最小的二叉排序樹。 舉例：舉例：形如滿二叉樹或完全二叉樹的形如滿二叉樹或完全二叉樹的二叉排二叉排序樹。序樹。 非常難于構(gòu)造。非常難于構(gòu)造。 折中：平衡二叉樹。折中：平衡二叉樹。平衡二叉樹 定義定義 ：它或者是一棵空二叉樹，或者是二叉樹它或者是一棵空二叉樹，或者是二叉樹中任一結(jié)點(diǎn)的左、右子樹高度之差的絕對(duì)

12、值不中任一結(jié)點(diǎn)的左、右子樹高度之差的絕對(duì)值不大于大于1，則稱這棵二叉樹為平衡二叉樹，則稱這棵二叉樹為平衡二叉樹 平衡因子平衡因子( (bfbf) )：結(jié)點(diǎn)的左、右子樹高度差為該：結(jié)點(diǎn)的左、右子樹高度差為該結(jié)點(diǎn)的平衡因子結(jié)點(diǎn)的平衡因子 平衡的二叉樹示例01-1001-1101 00不平衡的二叉樹示例210-1001-201 000平衡二叉樹的類型定義typedef struct AVLNode int key; int bf; /結(jié)點(diǎn)的平衡因子結(jié)點(diǎn)的平衡因子 struct AVLNode *lchild,*rchild; /左、右孩子指針左、右孩子指針 AVLNode ,*AVLTree; 構(gòu)造

13、平衡二叉樹 方法方法：每當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí)，首先檢查是否破每當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí)，首先檢查是否破壞了樹的平衡性，如果因插入結(jié)點(diǎn)而破壞了二壞了樹的平衡性，如果因插入結(jié)點(diǎn)而破壞了二叉排序樹的平衡，則找出其中叉排序樹的平衡，則找出其中最小不平衡子樹最小不平衡子樹。所謂最小不平衡子樹是指離插入結(jié)點(diǎn)最近，且所謂最小不平衡子樹是指離插入結(jié)點(diǎn)最近，且平衡因子的絕對(duì)值大于平衡因子的絕對(duì)值大于1的結(jié)點(diǎn)，因?yàn)榇私Y(jié)點(diǎn)的結(jié)點(diǎn)，因?yàn)榇私Y(jié)點(diǎn)失去平衡，使得該結(jié)點(diǎn)的祖先結(jié)點(diǎn)也可能隨之失去平衡，使得該結(jié)點(diǎn)的祖先結(jié)點(diǎn)也可能隨之失去平衡。所以，失衡后應(yīng)該調(diào)整以該結(jié)點(diǎn)為失去平衡。所以，失衡后應(yīng)該調(diào)整以該結(jié)點(diǎn)為根的子樹。根的子樹。失去平衡的

14、四種情況 321223131132LL型型RR型型失去平衡的四種情況 312233121132LR型型RL型型二叉平衡樹插入結(jié)點(diǎn) ( 結(jié)點(diǎn)旁的數(shù)字為其平衡因子 ) 示例15152127152121271521154327關(guān)鍵字的插入順序?yàn)殛P(guān)鍵字的插入順序?yàn)?15(15，2121，2727，4343，3636，8 8，11)11) RR示例關(guān)鍵字的插入順序?yàn)殛P(guān)鍵字的插入順序?yàn)?15(15，2121，2727，4343，3636，8 8，11)11) 2127154336212715368432127154336示例關(guān)鍵字的插入順序?yàn)殛P(guān)鍵字的插入順序?yàn)?15(15，2121，2727，4343，3

15、636，8 8，11)11) 15211136827431521364327118(i)(j)LL型調(diào)整操作示意圖BABRBLAR0BAARBLSBR21 (b)調(diào)整后恢復(fù)平衡調(diào)整后恢復(fù)平衡(a)插入結(jié)點(diǎn)插入結(jié)點(diǎn)S后失去平衡后失去平衡LL型調(diào)整的兩個(gè)例子01613125031251251631002(a) BL、BR、AR 都是空樹都是空樹 (b) BL、BR、AR 都是非空樹都是非空樹9281631254728925163147281631254701010000010000210RR型調(diào)整操作示意圖BBRAALBL (a) (a)插入結(jié)點(diǎn)插入結(jié)點(diǎn)* *s s后失去平衡后失去平衡(b)(b)

16、調(diào)整后恢復(fù)平衡調(diào)整后恢復(fù)平衡AAL-2BBRBL-1SRR型調(diào)整的兩個(gè)例子(a) A(a) AL L、B BL L、B BR R 都是空樹都是空樹69-1314703147-1473169000-20025470-1-2-100473169254700-100000-1031766940402576316940(b) A(b) AL L、B BL L、B BR R 都是非空樹都是非空樹LR型調(diào)整操作示意圖(b) (b) 調(diào)整后恢復(fù)平衡調(diào)整后恢復(fù)平衡 CACRAR0BBLCL00BAARCLCR2-1BLCS (a) (a) 插入結(jié)點(diǎn)插入結(jié)點(diǎn)* *s s后失去平衡后失去平衡 LR型調(diào)整的三個(gè)例子

17、281312503125-128253100020261628253147312547-10226281610031254700128160000000-10 (b) LR(L) (b) LR(L)型調(diào)整型調(diào)整(a) LR(0)(a) LR(0)型調(diào)整型調(diào)整LR型調(diào)整的三個(gè)例子312547-102302816-1003125470012816000301628253147001000(c) LR(R)(c) LR(R)型調(diào)整型調(diào)整RL型調(diào)整操作示意圖 (b) (b)調(diào)整后恢復(fù)平衡調(diào)整后恢復(fù)平衡CBCRBRAALCLBAALBRCLSCCR (a) (a) 插入結(jié)點(diǎn)插入結(jié)點(diǎn)* *s s后失去平衡

18、后失去平衡 RL型調(diào)整的三個(gè)例子(a) RL(0) RL(0)型調(diào)整型調(diào)整40-13147031471403147000-20(b) RL(L)RL(L)型調(diào)整型調(diào)整31254701-236406910031254700-169400003625403147690000-10RL型調(diào)整的三個(gè)例子 (c) RL(R) (c) RL(R)型調(diào)整型調(diào)整31254701-24369400-1031254700-16940000432540314769001000AVLAVL樹上結(jié)點(diǎn)的插入樹上結(jié)點(diǎn)的插入 結(jié)點(diǎn)插入后，若平衡二叉樹失去了平衡，結(jié)點(diǎn)插入后，若平衡二叉樹失去了平衡，則要找到最小不平衡子樹則要找

19、到最小不平衡子樹 當(dāng)插入樹中后，修改有關(guān)結(jié)點(diǎn)的平衡因子當(dāng)插入樹中后，修改有關(guān)結(jié)點(diǎn)的平衡因子 如何判斷根的子樹是否失去平衡如何判斷根的子樹是否失去平衡 ，若失，若失去平衡則要作相應(yīng)的處理去平衡則要作相應(yīng)的處理AVLAVL樹查找分析樹查找分析 深度為深度為h h的平衡二叉樹所具有的最少結(jié)點(diǎn)的平衡二叉樹所具有的最少結(jié)點(diǎn)數(shù)數(shù)。 設(shè)以設(shè)以Nh表示深度為表示深度為h的平衡二叉樹中含有的最少的平衡二叉樹中含有的最少結(jié)點(diǎn)數(shù)。結(jié)點(diǎn)數(shù)。 N00，N1=1，N2=2，并且，并且NhNh-1+Nh-2+1。利用歸納法可證明：當(dāng)利用歸納法可證明：當(dāng)h0時(shí)，時(shí)，Nh=Fh+2-1。 含有含有n個(gè)結(jié)點(diǎn)的平衡二叉樹的最大深度

20、，即在個(gè)結(jié)點(diǎn)的平衡二叉樹的最大深度，即在AVL上進(jìn)行查找的時(shí)間復(fù)雜度為上進(jìn)行查找的時(shí)間復(fù)雜度為O(logn)。B-樹 1970年Bayer提出B-樹 多路平衡外查找樹。 前面討論的查找方法適用于組織規(guī)模較小、內(nèi)存中能容納的數(shù)據(jù)，是內(nèi)查找方法內(nèi)查找方法 B-B-樹樹是一種平衡平衡、有序有序、多路多路、動(dòng)態(tài)動(dòng)態(tài)的查的查找樹找樹，它是磁盤文件系統(tǒng)中索引技術(shù)常用的一種數(shù)據(jù)結(jié)構(gòu)形式，如磁盤管理系統(tǒng)中的目錄管理以及數(shù)據(jù)文件中的索引機(jī)構(gòu)大多采用B-樹B-樹 B-樹的定義 一棵一棵m階的階的B-B-樹樹，或?yàn)榭諛洌驗(yàn)闈M足下列特性的，或?yàn)榭諛?，或?yàn)闈M足下列特性的m叉樹：叉樹： (1)樹中每個(gè)結(jié)點(diǎn)至多有樹中每個(gè)

21、結(jié)點(diǎn)至多有m棵子樹；棵子樹； (2)若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹；若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹； (3)除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有棵子樹；除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有棵子樹； ( 4 ) 所 有 的 非 終 端 結(jié) 點(diǎn) 中 包 含 下 列 信 息 數(shù) 據(jù)所 有 的 非 終 端 結(jié) 點(diǎn) 中 包 含 下 列 信 息 數(shù) 據(jù)（n,P0,K1,P1,K2,P2,Kn,Pn），其中：），其中：Ki(i=1,n)為關(guān)鍵字，且為關(guān)鍵字，且Kikey0=k; /設(shè)置哨兵，下面用順序查找設(shè)置哨兵，下面用順序查找key1.keynum for(i=t-keynum; kkeyi;

22、 i-); /從后向前找第從后向前找第1個(gè)小于等于個(gè)小于等于k的關(guān)鍵字的關(guān)鍵字 if(i0&t-keyi=k) /查找成功，返回查找成功，返回t及及i *pos=i; return t; /結(jié)點(diǎn)內(nèi)查找失敗，但結(jié)點(diǎn)內(nèi)查找失敗，但t-keyikkeyi+1下一個(gè)查找結(jié)點(diǎn)應(yīng)為下一個(gè)查找結(jié)點(diǎn)應(yīng)為soni if(!t-soni) /*t為葉子，在葉子中仍未找到為葉子，在葉子中仍未找到k，則查找過程失敗，則查找過程失敗 return NULL; DiskReadt-soni; /從磁盤上讀入下一個(gè)查找的樹結(jié)點(diǎn)到內(nèi)存中從磁盤上讀入下一個(gè)查找的樹結(jié)點(diǎn)到內(nèi)存中 return SearchBTree(t-

23、soni,k,pos);/遞歸的繼續(xù)查找子樹遞歸的繼續(xù)查找子樹t-soni/ SearchBTree B-樹查找分析 在含有N個(gè)關(guān)鍵字的B-樹上進(jìn)行查找時(shí)，從根結(jié)點(diǎn)到關(guān)鍵字所在結(jié)點(diǎn)的路徑上涉及的結(jié)點(diǎn)數(shù)不超過 1log212Nm若N=1,999,999, m=199，則查找次數(shù)至多為4。B-樹查找長度分析 第一層至少有第一層至少有1個(gè)結(jié)點(diǎn)；個(gè)結(jié)點(diǎn)； 第二層至少有第二層至少有2個(gè)結(jié)點(diǎn)；個(gè)結(jié)點(diǎn)； 第三層至少有第三層至少有2* m/2 個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，依次類推，依次類推; 第第L+1層至少有層至少有2*( m/2 )L-1個(gè)結(jié)點(diǎn)；個(gè)結(jié)點(diǎn)； 而而L+1層的結(jié)點(diǎn)為葉子結(jié)點(diǎn)層的結(jié)點(diǎn)為葉子結(jié)點(diǎn),數(shù)量為數(shù)量為N

24、+1; N+1=2*( m/2 )L-1 ; 即即L=log m/2 (N+1)/2)+1 。2/m附：S=N+1的推導(dǎo)設(shè)設(shè)B-樹某結(jié)點(diǎn)的子樹數(shù)為樹某結(jié)點(diǎn)的子樹數(shù)為Ci，則該結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)，則該結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)Ni=Ci-1。對(duì)于有。對(duì)于有k個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的B-樹，有樹，有 Ni=(Ci-1)=Ci-k（1ik） （1） 因?yàn)橐驗(yàn)锽樹上的關(guān)鍵字?jǐn)?shù)，即樹上的關(guān)鍵字?jǐn)?shù)，即Ni=N （1ik） （2） 而而B-樹上的子樹數(shù)可這樣計(jì)算：每個(gè)結(jié)點(diǎn)（除根結(jié)點(diǎn)）樹上的子樹數(shù)可這樣計(jì)算：每個(gè)結(jié)點(diǎn)（除根結(jié)點(diǎn)）都是一棵子樹，設(shè)葉子（子樹）數(shù)為都是一棵子樹，設(shè)葉子（子樹）數(shù)為S；則；則 Ci=(k-1)+S （1ik

25、） （3） 綜合（綜合（1）（）（2）（）（3）式，有）式，有s=n+1。證畢。證畢。B-樹的插入 插入操作先要通過查找確定插入的位置，然后可按以下插入操作先要通過查找確定插入的位置，然后可按以下三種情形分別進(jìn)行處理：三種情形分別進(jìn)行處理： 情形情形2：插入關(guān)鍵字的結(jié)點(diǎn)在插入后，關(guān)鍵字的個(gè)數(shù)超過：插入關(guān)鍵字的結(jié)點(diǎn)在插入后，關(guān)鍵字的個(gè)數(shù)超過m-1，則，則進(jìn)行分裂處理。假設(shè)當(dāng)前處理的結(jié)點(diǎn)由進(jìn)行分裂處理。假設(shè)當(dāng)前處理的結(jié)點(diǎn)由q指向，以指向，以 為界，將結(jié)為界，將結(jié)點(diǎn)點(diǎn)*q分裂成兩個(gè)結(jié)點(diǎn)，前面分裂成兩個(gè)結(jié)點(diǎn)，前面 - -1個(gè)關(guān)鍵字組成一部分仍由個(gè)關(guān)鍵字組成一部分仍由q指指向，其余后面的一部分由向，其余

26、后面的一部分由q1指向，而中間的一個(gè)關(guān)鍵字指向，而中間的一個(gè)關(guān)鍵字 帶著帶著指針指針ql被被“上擠上擠”到雙親結(jié)點(diǎn)中到雙親結(jié)點(diǎn)中。 2/m2/m2/mK情形情形3：在執(zhí)行情形：在執(zhí)行情形2的的“上擠上擠”處理后，雙親結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)處理后，雙親結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)也超過了也超過了m- -1個(gè)，則必須以該雙親結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)，進(jìn)行相同的處個(gè)，則必須以該雙親結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)，進(jìn)行相同的處理，也就是說要繼續(xù)理，也就是說要繼續(xù)“上擠上擠”直至根結(jié)點(diǎn)。一旦根結(jié)點(diǎn)中的關(guān)鍵字直至根結(jié)點(diǎn)。一旦根結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)超過了個(gè)數(shù)超過了m- -1個(gè)，對(duì)根結(jié)點(diǎn)進(jìn)行分裂處理后，整個(gè)個(gè)，對(duì)根結(jié)點(diǎn)進(jìn)行分裂處理后，整個(gè)B-樹的層數(shù)

27、即樹的層數(shù)即增加一層增加一層 情形情形1：插入關(guān)鍵字的結(jié)點(diǎn)在插入后，關(guān)鍵字的個(gè)數(shù)不超過：插入關(guān)鍵字的結(jié)點(diǎn)在插入后，關(guān)鍵字的個(gè)數(shù)不超過m-1，則將給定的關(guān)鍵字插入到該結(jié)點(diǎn)的相應(yīng)位置，插入過程即完成。則將給定的關(guān)鍵字插入到該結(jié)點(diǎn)的相應(yīng)位置，插入過程即完成。插入結(jié)點(diǎn)后的分裂 插入后插入后：m,P0,(K1,P1,),(Km,Pm); KiKi+1 (1=im) 分成分成*p和和*q兩個(gè)結(jié)點(diǎn)兩個(gè)結(jié)點(diǎn): p: m/2 -1,P0,(K1,P1),(K m/2 -1 ,P m/2 -1) q: m- m/2 ,P m/2 ,(K m/2 +1,P m/2 +1),(Km,Pm) K m/2 和和p一起插入

28、到一起插入到P結(jié)點(diǎn)中。結(jié)點(diǎn)中。B-樹上插入結(jié)點(diǎn)3階階B-樹上插入結(jié)點(diǎn)樹上插入結(jié)點(diǎn)5618 24q2031q1(c)561881(e)18 56 81bt(d)561820 24 31q(b)24 315618(a)插入結(jié)點(diǎn)示例5618 3572(a)5618 3572 83(b)5672 8318 21 35(c)21 561872 8335(d)插入結(jié)點(diǎn)示例21 56183569 72 83(e) 56217218356983(g)(f) 21 56 7218356983B-B-樹的刪除樹的刪除 在在B-B-樹樹上刪除一個(gè)關(guān)鍵字，則首先要找到該關(guān)上刪除一個(gè)關(guān)鍵字，則首先要找到該關(guān)鍵字所在的結(jié)

29、點(diǎn)，并從中刪除之。若該結(jié)點(diǎn)為鍵字所在的結(jié)點(diǎn)，并從中刪除之。若該結(jié)點(diǎn)為最下層的非終端結(jié)點(diǎn)，且其中的關(guān)鍵字個(gè)數(shù)不最下層的非終端結(jié)點(diǎn)，且其中的關(guān)鍵字個(gè)數(shù)不少于少于 ，則刪除完成。否則要進(jìn)行，則刪除完成。否則要進(jìn)行“合并合并”結(jié)點(diǎn)的操作。假如所刪除的關(guān)鍵字不是最下層結(jié)點(diǎn)的操作。假如所刪除的關(guān)鍵字不是最下層的某個(gè)非終端結(jié)點(diǎn)的某個(gè)非終端結(jié)點(diǎn)Ki，則可以指針，則可以指針Pi所指子樹中所指子樹中的最下層的非終端結(jié)點(diǎn)中的最小關(guān)鍵字的最下層的非終端結(jié)點(diǎn)中的最小關(guān)鍵字y與與Ki互互換，然后在相應(yīng)的結(jié)點(diǎn)中刪除換，然后在相應(yīng)的結(jié)點(diǎn)中刪除Ki。因此只需討。因此只需討論刪除最下層的非終端結(jié)點(diǎn)中的關(guān)鍵字的情形。論刪除最下層的非終端結(jié)點(diǎn)中的關(guān)鍵字的情形。它可分三種情形分別進(jìn)行處理它可分三種情形分別進(jìn)行處理: :2/mB-B-樹的刪除樹的刪除情形情形1：被刪關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目不小于：被刪關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目不小于 ，則只需從，則只需從該結(jié)點(diǎn)中刪去該關(guān)鍵字該結(jié)點(diǎn)中刪去該關(guān)鍵字K，及相