數(shù)據(jù)結(jié)構(gòu)(c語言版)第8章 查找(5.26)

1、第9章 查 找 第第8章章 查找查找 8.1 靜態(tài)查找表靜態(tài)查找表8.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 8.3 哈希表哈希表 第9章 查 找 查找表查找表：由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合， 可利用任意數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。松散的關(guān)系。 關(guān)鍵字關(guān)鍵字：數(shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識列表中的一個(gè)或一組數(shù)據(jù)元素。如果一個(gè)關(guān)鍵字可以唯一標(biāo)識列表中的一個(gè)數(shù)據(jù)元素，則稱其為主關(guān)鍵字，否則為次關(guān)鍵字。第9章 查 找 查找：查找：根據(jù)給定的關(guān)鍵字值，在特定的列表中確定一個(gè)其關(guān)鍵字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在列表中的位置。查找可能成功或失敗。 查找算法中涉及到三類參量： 查找對象K（找什么）；

2、查找范圍L（在哪找）； K在L中的位置（查找的結(jié)果）。第9章 查 找 查找的操作：查找的操作：1、查某個(gè)數(shù)據(jù)元素是否存在。、查某個(gè)數(shù)據(jù)元素是否存在。2、檢索某、檢索某個(gè)特定數(shù)據(jù)元素的屬性。個(gè)特定數(shù)據(jù)元素的屬性。3、在查找表中插入一個(gè)數(shù)據(jù)元素。、在查找表中插入一個(gè)數(shù)據(jù)元素。4、從查找表中刪除某個(gè)數(shù)據(jù)元素。、從查找表中刪除某個(gè)數(shù)據(jù)元素。 查找的基本方法查找的基本方法可以分為兩大類，即比較式查找法比較式查找法和計(jì)計(jì)算式查找法算式查找法。其中比較式查找法比較式查找法又可以分為靜態(tài)查找表靜態(tài)查找表和動(dòng)動(dòng)態(tài)查找表態(tài)查找表，而計(jì)算式查找法計(jì)算式查找法也稱為HASH（哈希）查找法（哈希）查找法。 靜態(tài)查找表靜

3、態(tài)查找表：只作前兩種操作。：只作前兩種操作。 動(dòng)態(tài)查找表動(dòng)態(tài)查找表：查找過程中同時(shí)插入不存在或刪除已存在：查找過程中同時(shí)插入不存在或刪除已存在的某個(gè)元素。的某個(gè)元素。第9章 查 找 平均查找長度：平均查找長度：為確定數(shù)據(jù)元素在列表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值，稱為查找算法在查找成功時(shí)的平均查找長度。對于長度為n的列表，查找成功時(shí)的平均查找長度為： niiinnCPCPCPCPASL12211其中Pi為查找列表中第i個(gè)數(shù)據(jù)元素的概率，Ci為找到列表中第i個(gè)數(shù)據(jù)元素時(shí)，已經(jīng)進(jìn)行過的關(guān)鍵字比較次數(shù)。由于查找算法的基本運(yùn)算是關(guān)鍵字之間的比較操作，所以可用平均查找長度來衡量查找算法的

4、性能。 第9章 查 找 8.1.1 順序表的查找順序表的查找 順序查找法的特點(diǎn)是，用所給關(guān)鍵字與線性表中各元素的關(guān)鍵字逐個(gè)比較，直到成功或失敗。存儲(chǔ)結(jié)構(gòu)通常為順序結(jié)構(gòu)，也可為鏈?zhǔn)浇Y(jié)構(gòu)。 下面給出順序結(jié)構(gòu)有關(guān)數(shù)據(jù)類型的定義： typedef struct ElemType *elem; int length;SSTable;8.1 靜態(tài)查找表靜態(tài)查找表 第9章 查 找 查找過程：從最后一個(gè)記錄開始逐個(gè)比較。 int Search_Seq(SSTable ST,KeyType key)/*在順序表ST中順序查找其關(guān)鍵字等于key的元素，若找到，則函數(shù)值為該元素在表中的位置，否則為0*/ ST.el

5、em0.key=key; for(i=ST.length; !EQ(ST.elemi.key,key); -i); return i; ST.elem0起監(jiān)視哨。當(dāng)ST.length=1000時(shí)，平均時(shí)間減少一半。 第9章 查 找 下面用平均查找長度來分析一下順序查找算法的性能。假設(shè)列表長度為n，那么查找第i個(gè)數(shù)據(jù)元素時(shí)需進(jìn)行n-i+1次比較，即Ci=n-i+1。又假設(shè)查找每個(gè)數(shù)據(jù)元素的概率相等，即Pi=1/n， 則順序查找算法的平均查找長度為： niniiniiininnCnCPASL111) 1(21) 1(11 考慮到查找不成功的情況，不成功比較n+1次，設(shè)查找成功和不成功概率相同，則P

6、i = 1/2n;ASLss= (1/2n)* (n-i+1)+ (1/2n)* (n+1) = 3/4(n+1) 若查找概率不等時(shí)，將概率高的放在最后，即按概率遞增的順序存放，可提高查找效率。但實(shí)際上記錄的查找概率無法預(yù)測，可通過設(shè)一個(gè)訪問頻度域來解決該問題。第9章 查 找 8.1.2 有序表的查找有序表的查找 折半查找法又稱為二分法查找法，這種方法要求待查找的列表必須是按關(guān)鍵字大小有序排列的順序表。其基本過程是：p 將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，p如果兩者相等，則查找成功；p否則利用中間位置記錄將表分成前、后兩個(gè)子表，p如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子

7、表，p否則進(jìn)一步查找后一子表。p重復(fù)以上過程，直到找到滿足條件的記錄，查找成功，或直到子表不存在，查找不成功。第9章 查 找 圖8.1 折半查找示意圖 第9章 查 找 折半查找的算法如下： int Search_Bin(SSTable ST, KeyType key）/*在有序表ST中折半查找其關(guān)鍵字等于key的元素，若找到，則函數(shù)值為該元素在表中的位置*/ low = 1 ; high = ST.length; /*置區(qū)間初值*/ while ( low BST-data ) return Find( X, BST-rchild ); /*在右子樹繼續(xù)查找*/ else if( X data

8、 ) return Find( X, BST-lchild); /*在左子樹中繼續(xù)查找*/ else /* X = BST-data */ return BST; /*查找成功，返回找到結(jié)點(diǎn)的地址*/ 第9章 查 找 由于非遞歸函數(shù)的執(zhí)行效率高，可將“尾遞歸”函數(shù)改為迭代函數(shù) 。BiTree Find(TElemType X, BiTree BST ) while( BST ) if( X BST-data ) BST = BST-rchild; /*向右子樹中移動(dòng)，繼續(xù)查找*/ else if( X data ) BST = BST-lchild; /*向左子樹中移動(dòng)，繼續(xù)查找*/ else

9、 /* X = BST-data */ return BST; /*查找成功，返回結(jié)點(diǎn)的找到結(jié)點(diǎn)的地址*/ return NULL; /*查找失敗*/ 查找的效率決定于樹的高度 第9章 查 找 2. 二叉排序樹的插入和生成二叉排序樹的插入和生成 關(guān)鍵是要找到元素應(yīng)該插入的關(guān)鍵是要找到元素應(yīng)該插入的位置位置，可以采用與可以采用與Find類似的方法類似的方法p若二叉排序樹是空樹，則key成為二叉排序樹的根；p若二叉排序樹非空，則將key與二叉排序樹的根進(jìn)行比較， 如果key的值等于根結(jié)點(diǎn)的值，則停止插入； 如果key的值小于根結(jié)點(diǎn)的值，則將key插入左子樹； 如果key的值大于根結(jié)點(diǎn)的值，則將ke

10、y插入右子樹。第9章 查 找 例：在二叉排序樹中插入333333新插入的結(jié)點(diǎn)一定是新插入的結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)，且其位置一定是查找不，且其位置一定是查找不成功時(shí)指向最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子。成功時(shí)指向最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子。第9章 查 找 算法如下：算法如下：BiTree Insert( TElemType X, BiTree BST ) if( !BST ) /*若原樹為空，生成并返回一個(gè)結(jié)點(diǎn)的二叉搜索樹*/ BST = (BiTree) malloc(sizeof(BiTNode); BST-data = X; BST-lchild = BST-rchild = NULL;

11、 else /*開始找要插入元素的位置*/ if( X data ) BST-lchild = Insert( X, BST- lchild); /*遞歸插入左子樹*/ else if( X BST-data ) BST-rchild = Insert( X, BST- rchild); /*遞歸插入右子樹*/ else /* X已經(jīng)存在，什么都不做 */ return BST; 第9章 查 找 若從空樹出發(fā)經(jīng)過一系列的查找插入操作之后，可生成一棵二叉樹。 中序遍歷二叉排序樹可得到一個(gè)關(guān)鍵字的有序序列。一個(gè)無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個(gè)有序序列。又因?yàn)槊看尾迦朐谌~子，無需移動(dòng)其它

12、結(jié)點(diǎn)。所以二叉排序樹既具有類似于折半查找的性能，又可以使用鏈?zhǔn)浇Y(jié)構(gòu)，避免元素位置的移動(dòng)。 第9章 查 找 例：根據(jù)輸入序列45，24，53，45，12，24，28，90生成二叉排序樹452412532890第9章 查 找 p考慮三種情況： 要?jiǎng)h除的是葉結(jié)點(diǎn)：直接刪除，并再修改其父結(jié)點(diǎn)相應(yīng)指針-置為置為NULL3. 二叉排序樹的刪除二叉排序樹的刪除452412532890例：要?jiǎng)h除28fpppf第9章 查 找 p要?jiǎng)h除的結(jié)點(diǎn)只有一個(gè)孩子結(jié)點(diǎn)要?jiǎng)h除的結(jié)點(diǎn)只有一個(gè)孩子結(jié)點(diǎn): 將其將其父結(jié)點(diǎn)父結(jié)點(diǎn)的指針的指針指向指向要?jiǎng)h除結(jié)點(diǎn)的要?jiǎng)h除結(jié)點(diǎn)的孩子結(jié)點(diǎn)孩子結(jié)點(diǎn) 。3. 二叉排序樹的刪除二叉排序樹的刪除45

13、2412532890例：要?jiǎng)h除53fpp第9章 查 找 p 要?jiǎng)h除的結(jié)點(diǎn)有左、右兩棵子樹： 用另一結(jié)點(diǎn)替代被刪除結(jié)點(diǎn)：右子樹的最小元素 或者 左子樹的最大元素。3. 二叉排序樹的刪除二叉排序樹的刪除452412532890例：要?jiǎng)h除536080704524125328906080702、取、取左子樹中的最大元素左子樹中的最大元素替代替代 1、取、取右子樹中的最小元素右子樹中的最小元素替代替代 908070第9章 查 找 BiTree Delete ( TElemType X, BiTree BST ) BiTree p; if( !BST ) printf(要?jiǎng)h除的元素未找到); else i

14、f( X data ) BST-lchild = Delete( X, BST- lchild); /* 左子樹遞歸刪除 */ else if( X BST-data ) BST-rchild = Delete( X, BST- rchild); /* 右子樹遞歸刪除 */ else /*找到要?jiǎng)h除的結(jié)點(diǎn) */ 第9章 查 找 if( BST- lchild & BST- rchild ) /*被刪除結(jié)點(diǎn)有左右兩個(gè)子結(jié)點(diǎn) */ p = FindMin( BST- rchild ); /*在右子樹中找最小的元素填充刪除結(jié)點(diǎn)*/ BST-data = p-data; BST- rchild = D

15、elete( BST-data, BST- rchild); /*在刪除結(jié)點(diǎn)的右子樹中刪除最小元素*/ else /*被刪除結(jié)點(diǎn)有一個(gè)或無子結(jié)點(diǎn)*/ p = BST; if( !BST- lchild ) /* 有右孩子或無子結(jié)點(diǎn)*/ BST = BST- rchild; else if( !BST- rchild ) /*有左孩子或無子結(jié)點(diǎn)*/ BST = BST- lchild; free( p ); return BST; 第9章 查 找 4. 二叉排序樹的查找性能分析二叉排序樹的查找性能分析 圖圖8.4 二叉排序樹的不同形態(tài)二叉排序樹的不同形態(tài) 93371224534512243745

16、5393(a) 輸入關(guān)鍵字序列為45,24,53,12,37,93時(shí)的二叉排序樹(b) 輸入關(guān)鍵字序列為12,24,37,45,53,93時(shí)的單支二叉排序樹ASLa=1/61+2+2+3+3+3=14/6ASLb =1/61+2+3+4+5+6=21/6含有含有n n個(gè)結(jié)點(diǎn)的二叉排序樹的平均查找長度和樹的形態(tài)有關(guān)個(gè)結(jié)點(diǎn)的二叉排序樹的平均查找長度和樹的形態(tài)有關(guān)第9章 查 找 由上節(jié)可知，二叉排序樹結(jié)點(diǎn)的不同插入次序，將導(dǎo)致不同的深度和平均查找長度ASL 平衡二叉排序樹平衡二叉排序樹 933712245345122437455393(a) 輸入關(guān)鍵字序列為45,24,53,12,37,93時(shí)的二叉

17、排序樹(b) 輸入關(guān)鍵字序列為12,24,37,45,53,93時(shí)的單支二叉排序樹第9章 查 找 平衡二叉樹又稱為AVL樹。p 或者是空樹，p 或者任一結(jié)點(diǎn)左、右子樹高度差的絕對值不超過1。 結(jié)點(diǎn)的平衡因子（結(jié)點(diǎn)的平衡因子（balance factor）BF：BF = HL-HR 引入平衡二叉樹的目的是為了提高查找效率，其平均查找長度為O（log2n）。平衡二叉排序樹平衡二叉排序樹 第9章 查 找 圖8.5 平衡與不平衡的二叉排序樹 208070302560405011110006030255040120058100(a) 一棵平衡二叉排序樹(b) 一棵失去平衡的二叉排序樹第9章 查 找 不平

18、衡點(diǎn)是A，插入結(jié)點(diǎn)15 在A的左子樹左子樹的左邊左邊，因而叫 LL 插入，需要LL 旋轉(zhuǎn)旋轉(zhuǎn)。 6015302025604010000AB(a) 一棵平衡二叉排序樹(b) 插入15后 失去平衡302025604020110AB030152040250000BA01(c) 調(diào)整后的二叉排序樹平衡二叉排序樹的調(diào)整（平衡二叉排序樹的調(diào)整（1） (a) 插入新結(jié)點(diǎn)S后 失去平衡(b) 調(diào)整后恢復(fù)平衡ABBLBRARS21BABLARBRS00第9章 查 找 不平衡結(jié)點(diǎn)是A，插入結(jié)點(diǎn)70 在A的右子樹的右邊，因而叫 RR 插入，需要RR 旋轉(zhuǎn)旋轉(zhuǎn)。30607060302040251000AB(a) 一棵

19、平衡二叉排序樹(b) 插入70后失去平衡204025200AB0202560400000BA0(c) 調(diào)整后的二叉排序樹70111300（2）(a) 插入新結(jié)點(diǎn)S后失去平衡(b) 調(diào)整后恢復(fù)平衡ABBRBLALS21BABRALBLS00第9章 查 找 (a) 一棵平衡二叉排序樹507000103095204090801000B06085AC0000(b) 插入45后失去平衡507010103095204090802101B06085AC00000458595(c) 調(diào)整后的二叉排序樹45103090204080600001B05070C00001A00 不平衡結(jié)點(diǎn)是A，插入結(jié)點(diǎn)45 在A的左

20、子樹的右邊，因而叫 LR 插入，需要LR 旋轉(zhuǎn)旋轉(zhuǎn)。（3）第9章 查 找 (a) 插入新結(jié)點(diǎn)S后失去平衡(b) 調(diào)整后恢復(fù)平衡ABCLARS21CCR1BLCACLARCRS01B0BL第9章 查 找 (c) 調(diào)整后的二叉排序樹(a) 一棵平衡二叉排序樹(b) 插入55后失去平衡859550709010208040100003060A00B0000C859550709010208040200003060A11B000C15508595551030902040806000A05070C0001B00100（4） 不平衡結(jié)點(diǎn)是A，插入結(jié)點(diǎn)55在A的右子樹的左邊，因而叫 RL 插入，需要RL 旋轉(zhuǎn)旋

21、轉(zhuǎn)。第9章 查 找 (b) 調(diào)整后恢復(fù)平衡(a) 插入新結(jié)點(diǎn)S后失去平衡ABBRCRS21CCL1ALCACRALCLS01B0BR第9章 查 找 綜上所述，在一個(gè)平衡二叉排序樹上插入一個(gè)新結(jié)點(diǎn)S時(shí)，主要包括以下三步： （1） 查找應(yīng)插位置，同時(shí)記錄離插入位置最近的可能失衡結(jié)點(diǎn)A（A的平衡因子不等于0）。 （2） 插入新結(jié)點(diǎn)S，并修改從A到S路徑上各結(jié)點(diǎn)的平衡因子。 （3） 根據(jù)A、B的平衡因子，判斷是否失衡以及失衡類型， 并做相應(yīng)處理。 第9章 查 找 8.2.2 B-樹和樹和B+樹樹 1. m路查找樹路查找樹 與二叉排序樹類似，可以定義一種“m叉排序樹”，通常稱為m路查找樹。 一棵m路查找

22、樹，或者是一棵空樹，或者是滿足如下性質(zhì)的樹： (1) 每個(gè)結(jié)點(diǎn)最多有m棵子樹、 m-1個(gè)關(guān)鍵字，其結(jié)構(gòu)如下： nP0K1P1K2P2KnPn第9章 查 找 其中n為關(guān)鍵字個(gè)數(shù)，Pi(0in)為指向子樹根結(jié)點(diǎn)的指針， Ki(1in)為關(guān)鍵字。 (2） Ki37，所以找到結(jié)點(diǎn)C，又因?yàn)?05885，所以找到結(jié)點(diǎn)G，最后在結(jié)點(diǎn)G中找到58。如果要查找32，首先由根指針mbt找到根結(jié)點(diǎn)A，因?yàn)?225，所以找到結(jié)點(diǎn)E，又因?yàn)?03235，所以最后找到失敗結(jié)點(diǎn)f，表示32不存在，查找失敗。 在具體實(shí)現(xiàn)時(shí)， 采用如下結(jié)點(diǎn)結(jié)構(gòu)： parentnK1K2KnP0P1Pn第9章 查 找 3. B-樹的插入樹的插

23、入已知一棵3階B-樹如圖8.8(a)所示，要求插入52、20、49。插入52：首先查找應(yīng)插位置，即結(jié)點(diǎn)f中50的后面，如圖8.8(b)所示。插入20：直接插入后如圖8.8(c)所示，由于結(jié)點(diǎn)c的分支數(shù)變?yōu)?，超出了3階B-樹的最大分支數(shù)3，需將結(jié)點(diǎn)c分裂為兩個(gè)較小的結(jié)點(diǎn)。以中間關(guān)鍵字14為界，將c中關(guān)鍵字分為左、右兩部分，左邊部分仍在原結(jié)點(diǎn)c中，右邊部分放到新結(jié)點(diǎn)c中，中間關(guān)鍵字14插到其父結(jié)點(diǎn)的合適位置，并令其右指針指向新結(jié)點(diǎn)c，如圖8.8(d)所示。 插入插入49：直接插入后如圖8.8(e)所示。f結(jié)點(diǎn)應(yīng)分裂，分裂后的結(jié)果如圖8.8(f)所示。50插到其父結(jié)點(diǎn)e的key1處，新結(jié)點(diǎn)f的地址

24、插到e的ptr1處，e中ptr0不變，仍指向原結(jié)點(diǎn)f。此時(shí)，e仍需要分裂，繼續(xù)分裂后的結(jié)果如圖8.8(g)所示。53存到其父結(jié)點(diǎn)a的key2處，ptr2指向新結(jié)點(diǎn)e，ptr1仍指向原結(jié)點(diǎn)e 。 第9章 查 找 (a) 一棵3階B樹(b) 插入52 后(c) 插入20,結(jié)點(diǎn)c需要分裂(d) 結(jié)點(diǎn)c分裂后(e) 插入49, 結(jié)點(diǎn)f需要分裂(g) 結(jié)點(diǎn)e分裂后(f) 結(jié)點(diǎn)f分裂后,結(jié)點(diǎn) e 仍需要分裂48256 1437cdbabt53 8650 5258 7098efgh48256 1437cdbabt53 865058 7098efgh48256 14 203753 8650 5258 7098

25、cdbabtefghbt4814 2563753 8650 5258 7098cdbaefgh20c4814 2563753 8649 50 5258 7098cdbabtefgh20cbt4814 2563750 53 8658 7098cdbaefgh20c52f4948 5314 2563758 7098cdbabtfgh20c52f495086ee圖圖8.8B-樹的插入實(shí)例樹的插入實(shí)例 第9章 查 找 我們可以利用B-樹的插入方法，從空樹開始，逐個(gè)插入關(guān)鍵字，從而創(chuàng)建一棵B-樹。例如，已知關(guān)鍵字集為37， 70， 12， 45， 90， 3， 24， 61， 53， 要求從空樹開始，逐

26、個(gè)插入關(guān)鍵字，創(chuàng)建一棵3階B-樹。創(chuàng)建過程如圖8.9所示。 第9章 查 找 (a) 空樹37(b) 插入3737 70(c) 插入70(d) 插入12(e) 插入45(g) 插入3(h) 插入24(i) 插入61(j) 插入53(分裂前)37 703 12 24904512 37 70902434590243451270379024345 611270379024345 53 61127037(f) 插入9037 701290371245 70 904537 703 12904512 37 70371270371245 70分裂分裂分裂分裂圖8.9 從空樹開始，逐個(gè)插入關(guān)鍵字，創(chuàng)建一棵3階B-

27、樹 第9章 查 找 從上述B-樹的構(gòu)造過程可得出以下結(jié)論： （1） 由于B樹是“從葉往根”長，而根對每個(gè)分支是公用的， 所以不論根長到多“深”，各分支的長度同步增長，因而各分支是“平衡”的。 （2） 生長的幾種情況： 最底層某個(gè)結(jié)點(diǎn)增大，分支數(shù)不變且各分支深度也不變。 從最下層開始，發(fā)生單次或連續(xù)分裂，但根結(jié)點(diǎn)未分裂，此時(shí)分支數(shù)增1（最下層結(jié)點(diǎn)增1），但原分支深度不變，新分支深度與原分支相同。 從最下層開始，連續(xù)分裂，根結(jié)點(diǎn)也發(fā)生分裂，產(chǎn)生一個(gè)新的根結(jié)點(diǎn)，此時(shí)分支數(shù)仍增1（最下層結(jié)點(diǎn)增1），但新、舊分支均為原分支長度加1。 第9章 查 找 （3） 根的形成過程： 初始未分裂的根：關(guān)鍵字個(gè)數(shù)為0

28、m-1，分支數(shù)為0(空樹)。2m(失敗結(jié)點(diǎn)數(shù))。 由分裂形成的根：關(guān)鍵字個(gè)數(shù)為1m-1，分支數(shù)為 2m。 顯然，對非空的B-樹而言，根結(jié)點(diǎn)至少有兩棵子樹（包括由失敗結(jié)點(diǎn)構(gòu)成的子樹），這就是B-樹定義中提到的第2條性質(zhì)。 第9章 查 找 （4） 除根以外的非終端結(jié)點(diǎn)的形成過程：除根以外的非終端結(jié)點(diǎn)的形成過程： 由“滿結(jié)點(diǎn)”分裂而得。假設(shè)m階B-樹中p結(jié)點(diǎn)中已有m-1個(gè)關(guān)鍵字，當(dāng)再插入一個(gè)關(guān)鍵字后，結(jié)點(diǎn)中信息為：m, A0, (k1, A1), (k2, A2), , （km, Am），有m+1個(gè)分支，為保持m階（m個(gè)分支），應(yīng)將p結(jié)點(diǎn)分裂為關(guān)鍵字個(gè)數(shù)盡量相等的p結(jié)點(diǎn)和新結(jié)點(diǎn)p1（或者說從p中分出

29、一部分信息構(gòu)成p1）。分裂后p中剩余信息為：m/2-1, A0, (k1, A1), (k2, A2), , （km/2-1, Am/2-1），共有m/2-1個(gè)關(guān)鍵字，及這些關(guān)鍵字的m/2個(gè)左、右相鄰分支指針。 第9章 查 找 分裂出去的信息為：（k m / 2 , A m / 2 ）, （k m / 2 + 1, Am/2+1）, , （km, Am）， 共計(jì)m-(m/2-1) = m-m/2+1個(gè)關(guān)鍵字及其右指針，其中km/2上移到p的父結(jié)點(diǎn)中，其余信息存入新結(jié)點(diǎn)p1中，所以p1中信息為：m-m/2，Am/2, （km/2+1, Am/2+1）, , （km, Am）。顯然，分裂后的非終端

30、結(jié)點(diǎn)（除根結(jié)點(diǎn)）所含關(guān)鍵字最少，分支也最少，其中p的分支數(shù)為B1=m/2，p1的分支數(shù)為B2=m-m/2+1。容易證明，B1B2，所以，除根之外的所有非終端結(jié)點(diǎn)至少有m/2棵子樹，這就是B-樹定義中提到的第3條性質(zhì)。 第9章 查 找 4. 在在B-樹中刪除一個(gè)關(guān)鍵字樹中刪除一個(gè)關(guān)鍵字 1） 在最下層結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵字 圖8.10(a)所示為一棵4階B-樹(m = 4)，要求刪除11、53、39、64、27。 第9章 查 找 (1) 刪除11時(shí)，13與其右的指針左移即可，如圖8.10(b)所示。 (2) 刪除53后，如圖8.10(c)所示。 結(jié)論：被刪關(guān)鍵字所在結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目不小于被刪關(guān)鍵字

31、所在結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目不小于m/2m/2，則只需從該結(jié)點(diǎn)中刪去關(guān)鍵字則只需從該結(jié)點(diǎn)中刪去關(guān)鍵字KiKi和相應(yīng)指針和相應(yīng)指針AiAi，樹的其他部，樹的其他部分不變。分不變。 第9章 查 找 (3) 刪除39時(shí)，為保持其“中序有序”，可將父結(jié)點(diǎn)中43下移至39處，而將右兄弟中最左邊的47上移至原43處，如圖8.10(d)所示。 結(jié)論：被刪關(guān)鍵字所在結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目等于被刪關(guān)鍵字所在結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目等于m/2-1m/2-1，而，而與該結(jié)點(diǎn)相鄰的右兄弟（左兄弟）結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目大于與該結(jié)點(diǎn)相鄰的右兄弟（左兄弟）結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目大于m/2-1m/2-1，則需將，則需將右兄弟的最?。ㄗ笮值艿淖畲螅╆P(guān)鍵字右兄

32、弟的最?。ㄗ笮值艿淖畲螅╆P(guān)鍵字移至雙移至雙親結(jié)點(diǎn)中，而將親結(jié)點(diǎn)中，而將雙親結(jié)點(diǎn)中小于（或大于）且緊靠該上移關(guān)鍵雙親結(jié)點(diǎn)中小于（或大于）且緊靠該上移關(guān)鍵字的關(guān)鍵字字的關(guān)鍵字移至被刪關(guān)鍵字所在結(jié)點(diǎn)中。移至被刪關(guān)鍵字所在結(jié)點(diǎn)中。第9章 查 找 (4) 刪除64后，為保持各分支等長（平衡），將刪除64后的剩余信息(在此為空指針)及78合并入右兄弟，如圖8.10(e)所示。也可將刪除64后的剩余信息及47與左兄弟合并。 結(jié)論：被刪關(guān)鍵字所在結(jié)點(diǎn)和其相鄰的兄弟結(jié)點(diǎn)中的被刪關(guān)鍵字所在結(jié)點(diǎn)和其相鄰的兄弟結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目均等于關(guān)鍵字?jǐn)?shù)目均等于m/2-1m/2-1，設(shè)該結(jié)點(diǎn)有右兄弟且所在結(jié)點(diǎn)設(shè)該結(jié)點(diǎn)有右兄弟且所

33、在結(jié)點(diǎn)中剩余的關(guān)鍵字和指針，加上雙親中的中剩余的關(guān)鍵字和指針，加上雙親中的K Ki i一起，合并到一起，合并到A Ai i所所指兄弟結(jié)點(diǎn)中。指兄弟結(jié)點(diǎn)中。 第9章 查 找 (5) 刪除27時(shí)，首先將剩余信息(在此為空指針)與父結(jié)點(diǎn)中的18并入左兄弟，并釋放空結(jié)點(diǎn)，結(jié)果如圖8.10(f)所示。再將父結(jié)點(diǎn)中的剩余信息與祖父結(jié)點(diǎn)中的35并入47左端，釋放空結(jié)點(diǎn)后的結(jié)果如圖8.10(g)所示。至此，祖父結(jié)點(diǎn)仍需要合并，但由于待合并結(jié)點(diǎn)的父指針為NULL，故停止合并，直接將根指針bt置為指針p2的值，釋放空結(jié)點(diǎn)后的結(jié)果如圖8.10(h)所示。 第9章 查 找 (a) 一棵4 階B樹(b )刪除11 后(c) 刪除53 后(d) 刪除39 后(e) 刪除64 后(f) 刪除27 后,將剩余信息與父結(jié)點(diǎn)中的18并入左兄弟(g) 將父結(jié)點(diǎn)剩余信息與祖父結(jié)點(diǎn)中的35并入47左端(h) 刪除27 后的最終結(jié)果992711 1347 53 641843 783539