數(shù)據(jù)結(jié)構(gòu) 集合及查找詳細(xì)解析

1、計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系n集合集合n靜態(tài)查找靜態(tài)查找n哈希表哈希表 n二叉查找樹二叉查找樹nB樹和樹和B樹樹1計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系2計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系3計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系集合運算集合運算A B 或 A+BABABA B 或 A BABA- -B4計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系5計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系#include const int DefaultSize = 100;class Set private: int * bitVector; /集合的位向量數(shù)組 int Max

2、Size; /最大元素個數(shù)public: Set ( int MaxSetSize = DefaultSize ); Set ( ) delete bitVector; 6計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 void MakeEmpty ( ) /置空 for ( int i = 0; i 0 ); /判參數(shù)合理否 bitVector = new int MaxSize; /分配空間 assert ( bitVector != NULL ); for ( int i = 0; i = 0 & x = 0 & x MaxSize ) bitVectorx = 0; ret

3、urn 1; return 0; 010計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系void Set : operator = ( Set& right ) /賦值 assert ( MaxSize = right.MaxSize ); for ( int i = 0; i MaxSize; i+ ) /逐位傳送 bitVectori = right.bitVectori;this0 1 1 1 0 0 0 0 0 0 0right0 1 1 1 0 0 0 0 1 1 011計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系Set & Set : operator + ( Set&am

4、p; right ) /求并 assert ( MaxSize = right.MaxSize ); for ( int i = 0; i MaxSize; i+ ) bitVectori = bitVectori | right.bitVectori; return *this;thisrightthis0 1 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 1 1 1 0 1 0 1 1 1 012計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系Set & Set : operator * ( Set & right ) /求交 assert (

5、MaxSize = right.MaxSize ); for ( int i = 0; i MaxSize; i+) bitVectori = bitVectori &right.bitVectori; return *this;thisrightthis0 1 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 0 1 0 0 0 0 0 0 1 013計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系Set & Set : operator - ( Set & right ) /求差 assert ( MaxSize = right.MaxSiz

6、e ); for ( int i = 0; i = 0 & x MaxSize ); return bitVectorx;0 1 0 0 1 0 0 1 0 0 0 9315計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系int Set : operator = ( Set& right ) /判等 assert ( MaxSize = right.MaxSize ); for ( int i = 0; i MaxSize; i+) if ( bitVectori != right.bitVectori ) return 0; return 1;thisright0 0 1 1 0

7、0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 0i16計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系int Set : SubSet ( Set& right ) /判斷 this 是否是 right 的子集 assert ( MaxSize = right.MaxSize ); for ( int i = 0; i MaxSize; i+) if ( bitVectori & ! right.bitVectori) return 0; return 1;thisright0 0 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 0 0

8、 1 i17計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系若表中存在特定元素，稱查找成功，應(yīng)輸出該元素。若表中存在特定元素，稱查找成功，應(yīng)輸出該元素。- 否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）查找表查找表查查 找找查找成功查找成功查找不成功查找不成功靜態(tài)查找靜態(tài)查找動態(tài)查找動態(tài)查找關(guān)鍵字關(guān)鍵字主關(guān)鍵字主關(guān)鍵字次關(guān)鍵字次關(guān)鍵字由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。查詢查詢(Searching)特定元素特定元素是否在表中。是否在表中。只查找，不改變集合內(nèi)的數(shù)據(jù)元素。只查找，不改變集合內(nèi)的數(shù)據(jù)元素。既

9、查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素。既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素。元素中某個數(shù)據(jù)項的值，可用來識別一個元素元素中某個數(shù)據(jù)項的值，可用來識別一個元素 可以可以唯一唯一標(biāo)識一個元素的關(guān)鍵字標(biāo)識一個元素的關(guān)鍵字 例如例如“學(xué)號學(xué)號”例如例如“性別性別”識別若干元素的關(guān)鍵字識別若干元素的關(guān)鍵字 基本概念基本概念18計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系v 對查找表常用的操作有對查找表常用的操作有哪些？哪些？ v查詢查詢某個某個“特定的特定的”數(shù)據(jù)元素是否在表中；數(shù)據(jù)元素是否在表中；v在查找表中在查找表中插入插入一元素；一元素；v從查找表中從查找表中刪除刪除一元素。一元素。 v查找的過程

10、是怎樣的？查找的過程是怎樣的？ 19計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系v如何評估查找算法的優(yōu)劣？如何評估查找算法的優(yōu)劣？ 查找的過程就是將給定的查找的過程就是將給定的K值與值與查找表查找表中各元素的關(guān)鍵字進(jìn)中各元素的關(guān)鍵字進(jìn)行比較的過程。所以用比較次數(shù)的平均值來評估算法的優(yōu)劣，行比較的過程。所以用比較次數(shù)的平均值來評估算法的優(yōu)劣，稱為稱為平均查找長度平均查找長度（ASL：average search length）。）。顯然，顯然，ASL值越小，時間效率越高。值越小，時間效率越高。 niiniiisuccpcpASL11) 1 ( .20計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系21計

11、算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系template int searchList : Search ( const Type& x ) const /順序搜索關(guān)鍵碼為 x 的對象, 第CurrentSize號/位置作為控制搜索自動結(jié)束的“監(jiān)視哨”使用 ElementCurrentSize.key = x; int i = 0; /將x送CurrentSize號位置設(shè)監(jiān)視哨 while ( Elementi.key != x ) i+; /從前向后順序搜索 return i;22計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 1010niiniiisuccpcpASL) 1 ( .)(

12、110ipASL-niisucc23計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系.)()(1-nisuccnnnninASL02121111順序查找的優(yōu)缺點：順序查找的優(yōu)缺點： 優(yōu)點：對表中元素沒有要求優(yōu)點：對表中元素沒有要求 缺點缺點: 平均查找長度較大平均查找長度較大24計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系25計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系- -1 0 1 3 4 6 8 10 1260 1 2 3 4 5 6 7 8lowmidhigh6搜索成功的例子搜索成功的例子66low mid high5 6 8 10 125 6 7 8low midhigh626計算機學(xué)院計算機

13、學(xué)院 軟件工程系軟件工程系- -1 0 1 3 4 6 8 10 1250 1 2 3 4 5 6 7 8lowmidhigh5搜索失敗的例子搜索失敗的例子655low mid high 6 8 10 125 6 7 8low midhigh527計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系BinarySearch ( const Type & x, const int low, const int high ) const /折半搜索的遞歸算法 int mid = -1; if ( low = high ) mid = ( low + high ) / 2; if ( Elementm

14、id.key x ) mid = BinarySearch ( x, low, mid -1 ); return mid;28計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系template int orderedList : BinarySearch ( const Type & x ) const / int high = CurrentSize-1, low = 0, mid; while ( low = high ) mid = ( low + high ) / 2; if ( Elementmid.key x ) high = mid - 1; /左縮搜索區(qū)間 else retur

15、n mid; /搜索成功 return -1; /搜索失敗29計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系算法分析：算法分析：orderT: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 2 4 6 8 10 13 15 18 20 22 24 25 27 30 156241081324202718222530折半查找的判定樹：比較次數(shù)不超過完全二叉樹高度。折半查找的判定樹：比較次數(shù)不超過完全二叉樹高度。30計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系最多的比較次數(shù)不超過二叉樹的高度：所以最多的比較次數(shù)不超過二叉樹的高度：所以最壞情況下最壞情況下的查找長度是：的查找長度是：折半折

16、半查找成功查找成功的平均查找長度：的平均查找長度： 設(shè)查找任一元素的概率都相等，即：設(shè)查找任一元素的概率都相等，即：pi=1/n 在第在第k層上最多有層上最多有2k-1 個結(jié)點，在第個結(jié)點，在第k層上的結(jié)點需層上的結(jié)點需比較比較k次。所以：次。所以： )1n(log)n(T2 niiniiisuccpcpASL11) 1 ( niisucccASL1n131計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系)2*h2*)1h(.2*32*21*1(n12*kn1cn1ASL1h2h211kh1kin1isucc 12)1h(2h2)1h( 232211h1h2h21 nlog1) 1n(logn1n

17、)n) 1n(log) 1n(n1) 12) 1h(n1 ASL222hsucc 32計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 ( 10, 20, 30, 40, 50, 60 )105030204060ASLunsucc = (2*1+3*6)/7 = 20/7 ASLsucc = (1+2*2+ 3*3)/6 = 14/6 33計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系索引順序表的查找索引順序表的查找(分塊查找分塊查找)1. 概念：是順序查找的一種改進(jìn)。概念：是順序查找的一種改進(jìn)。索引項索引項：(key,addr), key 是關(guān)鍵字，是關(guān)鍵字，addr是地址。是地址。索引表：索引表：由

18、索引項構(gòu)成的順序表。由索引項構(gòu)成的順序表。22 15 13 8 17 20 35 24 33 40 36 29 50 48 60 68 54 6122 40 680 6 12最大關(guān)鍵字最大關(guān)鍵字(key)起始地址起始地址(addr)如何查找關(guān)鍵字為如何查找關(guān)鍵字為60的元素的元素?34計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系分塊查找的算法思想：分塊查找的算法思想：D=d1,d2,.,dn1) 將數(shù)據(jù)集分為將數(shù)據(jù)集分為s個塊個塊 B1,B2, , Bs ；2) 塊間有序：當(dāng)塊間有序：當(dāng)ij時，時，Bi中的任一元素小于中的任一元素小于Bj中的任中的任 一元素；一元素；3) 為每個為每個Bi塊設(shè)一

19、索引項塊設(shè)一索引項(keyi, addri)；4) s個索引項構(gòu)成索引表；個索引項構(gòu)成索引表；5) 塊內(nèi)可有序可無序塊內(nèi)可有序可無序;35計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系查找過程查找過程:（1）首先在索引表中查找，確定在哪個塊中。）首先在索引表中查找，確定在哪個塊中。 可以是折半查找，也可以是順序查找?？梢允钦郯氩檎?，也可以是順序查找。（2）在塊中查找。在塊中查找只能是順序查找。）在塊中查找。在塊中查找只能是順序查找。36計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系4. 算法分析：算法分析：設(shè)在索引表中和塊內(nèi)都是順序查找。設(shè)在索引表中和塊內(nèi)都是順序查找。(s是索引項的數(shù)目是索引項的數(shù)目

20、)索引表中查找：索引表中查找：ALSindex=(s+1)/2塊中查找：塊中查找： ALSlock=(n/s+1)/2所以：所以： ALSbs= (s+1)/2 + (n/s+1)/2顯然它與顯然它與s 的取值有關(guān)。的取值有關(guān)。當(dāng)當(dāng) 時，時，ASL有最小值有最小值 ns 1n例如例如 當(dāng)當(dāng)n=28，s=24時，時，ASLbs=17, 而折半法為而折半法為8， 順序表為順序表為(28+1)/2=128.537計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 對象關(guān)鍵碼 key 對象存放地址 addr38計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系39計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系性別次索引次

21、關(guān)鍵碼次關(guān)鍵碼 男男 女女 計計 數(shù)數(shù) 5 3 地址指針地址指針指針指針 03 08 17 24 47 51 83 9540計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系婚否次索引次關(guān)鍵碼次關(guān)鍵碼 已婚已婚 未婚未婚 計計 數(shù)數(shù) 5 3 地址指針地址指針指針指針 03 08 24 47 83 17 51 95職務(wù)次索引次關(guān)鍵碼次關(guān)鍵碼 教師教師 教務(wù)員教務(wù)員 實驗員實驗員 計計 數(shù)數(shù) 5 1 2 地址指針地址指針指針指針 08 24 47 51 83 03 17 9541計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系42計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系43計算機學(xué)院計算機學(xué)院 軟件工程系軟件

22、工程系44計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系45計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系46計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系47計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系48計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系49計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 rikikrn12)/( ki50計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系51計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系52計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系53計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系54計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 標(biāo)識符的八進(jìn)制內(nèi)碼表示及其平方值標(biāo)識符的八進(jìn)制內(nèi)碼表示

23、及其平方值55計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系56計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系57計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 58計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系59計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 60計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系61計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系62計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系63計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系A(chǔ)ttlee Burke Broad Blum EkersAlton Ederly Hecht 64計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系65計算機學(xué)院計算機學(xué)院 軟件

24、工程系軟件工程系66計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系67計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系j = (H0 - i2 ) % m, if ( j 0 ) j += m68計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系0 1 2 3 4 5 Blum Burke Broad Ekers Ederly Hecht 6 7 8 9 10 11 Alton Attlee (3) (1) (2) (1) (2)(1)25 26 27 28 29 30 (5) (3)69計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系70計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系71計算機學(xué)院計算機學(xué)院 軟件工程系

25、軟件工程系72計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 (1) (3) (1) (2) (1) (1) (2) (6) 0 1 2 3 4 5 6 7 8 9 10 1 8 2 5 3 4 6 773計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系74計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系75計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系A(chǔ)ttleeAltonBurkeBroadBlumEkersEderly76計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 77計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系35154550402510203078計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系二叉鏈表二叉鏈表

26、79計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系80計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系35154550402510203081計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系35154550402510203028插入新結(jié)點插入新結(jié)點2882計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 53537853786553786517537865871753786509178753786581178709537865151787098183計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系12311113222332384計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系85計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系5

27、378651787092345刪除45右子樹空, 用左子女頂替5378651787092386計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系53788817940923刪除78左子樹空, 用右子女頂替53948817092387計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系刪除78在右子樹上找中序下第一個結(jié)點填補8853788117940945236553818817940945236588計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 ABCABCDEDE89計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系90計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系91計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系92計算機學(xué)

28、院計算機學(xué)院 軟件工程系軟件工程系93計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系插入插入ACEBDhhh-1 h-1BACEDhhh-1 hBhhCEADh-1 h94計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系h插入插入BACEDhhh-1hhhh-1h-1ABDCEhhh-1BCEADh95計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系插入插入hhACEDh-1h-1BFGEGACDBFhhh-1h96計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系A(chǔ)EhhCDh-1hBFGFGDhAh-1CEBhh97計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系hhh-1h-1ACEDBFGACEBFGDhhhh-1

29、98計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系A(chǔ)CEDBFGhhh-1hhhh-1hACEBFGD99計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系100計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系161633163111631691116331611931126916101計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系18167326119316971126183716142691173918261116102計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系151831816731171491615112626149103計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系104計算機學(xué)院計算機學(xué)院 軟件工程系軟件工

30、程系105計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系0hhh-1不旋轉(zhuǎn)1hh-1pp106計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系- -1h+1hh不旋轉(zhuǎn)0hhpp高度減1107計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系108計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系1hhh-1左單旋ph0q1hh-1phq- -1109計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系1hh-1左單旋ph1q0h-1phq0h-1h-1110計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系01hh-1p- -1qh-1或h-2h-1或h-2h-1rh-1h-1h-1h-100pqr右左雙旋高度減1111計算機學(xué)院計算機

31、學(xué)院 軟件工程系軟件工程系A(chǔ)BCDEFGHIJKLMNOPQRST0000000- -1- -1- -1- -1- -1- -1- -111111112計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系A(chǔ)BCDEFGHIJKLMNOPQRST0000000- -1- -1- -1- -1- -1- -1- -111111POOPOOP113計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系A(chǔ)BCDEFGHIJKLMNOQRST000000- -1- -1- -1- -1- -1- -1- -111111RM114計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系A(chǔ)BCDEFGHIJKLMNOQRST000000- -

32、1- -1- -1- -1- -1- -1- -11001 MMME0115計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系A(chǔ)BCDEFGHIJNKLMOR00000- -100- -1- -1- -1- -1010000TQ0S116計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系117計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系3520 40abcde25 3010 1545 50118計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系3520 40abcde25 3010 1545 50root119計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系120計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系121計算機學(xué)院計算

33、機學(xué)院 軟件工程系軟件工程系303520 4025 3010 1545 50root45 50354020root10 1525122計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 123計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系124計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系125計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系126計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系n 127計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系1.空樹，插入根；結(jié)束；否則：空樹，插入根；結(jié)束；否則：2.找到插入位置找到插入位置 (p,i) , p在它最底層；在它最底層；3. 將將key 插入到（插入到（p,i）處；）處

34、；4. 若若p中中key多于多于m-1，按如下方法分裂，否則結(jié)束，按如下方法分裂，否則結(jié)束.128計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 若若p不是根：不是根： K1 K2 . Ki-1 Ki Ki+1 . Km 2/mi p K1 K2 . Ki-1Ki+1 . Km K1 Ki K KiP P一分為二一分為二P P的雙親的雙親129計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 若若p是根：是根： K1 K2 . Ki-1 Ki Ki+1 . Km 2/mi p K1 K2 . Ki-1Ki+1 . Km Ki KiP P一分為二一分為二創(chuàng)建新的根創(chuàng)建新的根130計算機學(xué)院計算機學(xué)院 軟件

35、工程系軟件工程系n=1 加入加入5353n=2 加入加入7553 75n=3 加入加入1397513953n=5 加入加入49,14575139 14549 53131計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系n=7 加入加入1014953361391451017549 75n=6 加入加入36139 1455336132計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系133計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系1. 找到被刪除的找到被刪除的key 所在的位置所在的位置（p, i）/即即p.keyi;2. p不是最底層結(jié)點：不是最底層結(jié)點： 用用p的子樹的子樹ptri中的最小鍵中的最小鍵key1

36、，代替，代替key， 問題變?yōu)閯h除問題變?yōu)閯h除key1，類似地逐次用下一層的替類似地逐次用下一層的替代當(dāng)前的代當(dāng)前的key，直至底層，使被刪除鍵落在最底，直至底層，使被刪除鍵落在最底層，層，p指向該結(jié)點指向該結(jié)點 例：例：4階階B-樹樹 。15 208 1217 25 30 16 18 。p134計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系3. p是最底層結(jié)點：是最底層結(jié)點：36 49m = 3刪除3649135計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系55 5875 80m = 3刪除5510406560 703050acbdefgh5875 8010406560 703050acbdefgh

37、136計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系不少于不少于8 126 10 14 18刪除刪除10108 146 12 18對稱地也可以將左兄弟中的最大鍵右旋移動對稱地也可以將左兄弟中的最大鍵右旋移動137計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系138計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系5580m = 3刪除5510406058 753050acbdefgh合并f, g58 60801040753050acbdefh139計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系8055m = 3刪除8010406058 753050acbdefgh合并g, h60 75551040583050ac

38、bdefh140計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系55 5875 80完整示例完整示例：m = 3刪除5010406560 703050acbdefgh用55取代555875 80刪除5510406560 7030acbdefgh用58取代141計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系5875 8010406560 7030acbdefgh合并f, g5875 80104060 657030acbdefh142計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系5880104060 657530acbdefh刪除70用75取代58104060 658030acbdefh刪除75用80取代調(diào)整f

39、, c, h143計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系58801040606530acbdefh8030 4060fh58 65db144計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系145l B+樹是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種樹是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種B-樹的變樹的變形樹。形樹。l 一棵一棵m階的階的B+樹和樹和m階的階的B-樹的差異在于：樹的差異在于：有有n棵子樹的結(jié)點中含有棵子樹的結(jié)點中含有n個關(guān)鍵碼；個關(guān)鍵碼；所有的葉子結(jié)點中包含了全部關(guān)鍵碼的信息，所有的葉子結(jié)點中包含了全部關(guān)鍵碼的信息，及指向含有這些關(guān)鍵碼記錄的指針，且葉子結(jié)點及指向含有這些關(guān)鍵碼記錄的指針，且葉子結(jié)點本身依關(guān)

40、鍵碼的大小自小而大的順序鏈接。本身依關(guān)鍵碼的大小自小而大的順序鏈接。所有的非終端結(jié)點可以看成是索引部分，結(jié)點所有的非終端結(jié)點可以看成是索引部分，結(jié)點中僅含有其子樹根結(jié)點中最大（或最小）關(guān)鍵碼中僅含有其子樹根結(jié)點中最大（或最?。╆P(guān)鍵碼。計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系146B樹索引是一個多級索引樹索引是一個多級索引(1)B樹結(jié)點結(jié)構(gòu)樹結(jié)點結(jié)構(gòu) P1 K1 P2 Pn-1 K n-1 P n 有有n-1個搜索碼個搜索碼K1 、K2 、Kn-1 ，n個個 指針指針P1 、Pn 。 結(jié)點中碼值結(jié)點中碼值有序存放有序存放：如果：如果ij ,則則Ki Kj 。計算機學(xué)院計算機學(xué)院 軟件工程系軟件

41、工程系(2)葉結(jié)點結(jié)構(gòu)，對于葉結(jié)點結(jié)構(gòu)，對于i=1,2, ，n-1。指針。指針Pi 指向指向具有具有Ki 的一個文件記錄（主索引文件按照碼值的一個文件記錄（主索引文件按照碼值存放）或指向一個指針桶（輔助索引），桶中存放）或指向一個指針桶（輔助索引），桶中每個指針指向具有碼值每個指針指向具有碼值Ki 的一個文件記錄。指的一個文件記錄。指針針Pn 指向下一個葉結(jié)點的頭指針。這樣可以將指向下一個葉結(jié)點的頭指針。這樣可以將葉結(jié)點按照碼值順序串在一起，以便對文件進(jìn)葉結(jié)點按照碼值順序串在一起，以便對文件進(jìn)行順序處理。行順序處理。 葉結(jié)點中最多有葉結(jié)點中最多有n-1個碼值，至少有個碼值，至少有 (n-1)/

42、2 個個碼值，各葉結(jié)點中值地范圍互不相交，即若碼值，各葉結(jié)點中值地范圍互不相交，即若Li 和和Lj 是兩個葉結(jié)點且是兩個葉結(jié)點且ij ，那么，那么Li 中的所有中的所有碼值都小于碼值都小于Lj 中的所有碼值。中的所有碼值。 要使要使B樹索引成為稠密索引，各碼值必須出樹索引成為稠密索引，各碼值必須出現(xiàn)在葉結(jié)點中?，F(xiàn)在葉結(jié)點中。 147計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系(3)B樹的非葉結(jié)點，形成葉結(jié)點上的一個樹的非葉結(jié)點，形成葉結(jié)點上的一個多級（稀疏）索引。對于多級（稀疏）索引。對于i=2,3, ，n-1，指針指針Pi 指向一棵子樹，該子樹中所有結(jié)點指向一棵子樹，該子樹中所有結(jié)點的索引碼值

43、大于等于的索引碼值大于等于Ki1 且小于且小于Ki ，Pn 指指向的子樹中所有碼值大于等于向的子樹中所有碼值大于等于Kn-1 ，P1 指指向子樹中的所有碼值均小于向子樹中的所有碼值均小于K1 。 非葉結(jié)點中至少有非葉結(jié)點中至少有 n/2 個指針，最多有個指針，最多有n個，指針個數(shù)稱為該結(jié)點的扇出。個，指針個數(shù)稱為該結(jié)點的扇出。148計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系(4)根結(jié)點：根結(jié)點的指針數(shù)可以小于根結(jié)點：根結(jié)點的指針數(shù)可以小于 n/2 。 除非整棵樹只有一個結(jié)點，否則，根結(jié)點至少除非整棵樹只有一個結(jié)點，否則，根結(jié)點至少有兩個指針。完整的有兩個指針。完整的B樹。如圖：樹。如圖：roo

44、t sqt 59 97 15 44 5972 97 10 15 21 37 4451 5963 72 85 91 97149計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 通常在通常在B+樹上有樹上有兩個頭指針兩個頭指針，一個指向，一個指向根結(jié)點，另一個指向關(guān)鍵碼最小的葉子根結(jié)點，另一個指向關(guān)鍵碼最小的葉子結(jié)點結(jié)點 。 因此，可以對因此，可以對B+樹進(jìn)行樹進(jìn)行兩種查找運算兩種查找運算：一種是從最小關(guān)鍵碼起順序查找，另一一種是從最小關(guān)鍵碼起順序查找，另一種是根結(jié)點開始，進(jìn)行隨機查找。種是根結(jié)點開始，進(jìn)行隨機查找。150計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 在在B +樹上進(jìn)行隨機查找、插入和刪除

45、的樹上進(jìn)行隨機查找、插入和刪除的過程基本上與過程基本上與B-樹類似。樹類似。 在查找時，若非終端結(jié)點上的關(guān)鍵碼等在查找時，若非終端結(jié)點上的關(guān)鍵碼等于給定值，并不終止，而是繼續(xù)向下直于給定值，并不終止，而是繼續(xù)向下直到葉子結(jié)點。因到葉子結(jié)點。因 此，此，在在B+樹，不管查找樹，不管查找成功與否，每次查找都是走了一條從根成功與否，每次查找都是走了一條從根到葉子結(jié)點的路徑到葉子結(jié)點的路徑。 B+樹查找的分析類似于樹查找的分析類似于B-樹。樹。151計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 B樹的插入樹的插入 B樹的插入僅在葉子結(jié)點上進(jìn)行，當(dāng)結(jié)樹的插入僅在葉子結(jié)點上進(jìn)行，當(dāng)結(jié)點中的關(guān)鍵字個數(shù)大于點中的關(guān)鍵字個數(shù)大于m時要分裂成兩時要分裂成兩個結(jié)點，它們所含關(guān)鍵字的個數(shù)分別為個結(jié)點，它們所含關(guān)鍵字的個數(shù)分別為 和和 。并且，它們的雙親結(jié)點中。并且，它們的雙親結(jié)點中應(yīng)同時包含這兩個結(jié)點中的最大關(guān)鍵字應(yīng)同時包含這兩個結(jié)點中的最大關(guān)鍵字。其余同。其余同B-樹的插入類似。樹的插入類似。15221m2m計算機學(xué)院計算機學(xué)院 軟件工程系軟件工程系 B樹的刪除樹的刪除 B樹的