【正文】 樹(shù)的平衡。 數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 0 0 1 在 A的右子樹(shù)的左子樹(shù)上增 加一個(gè)結(jié)點(diǎn) 2 1 1 順時(shí)針旋轉(zhuǎn) 逆時(shí)針旋轉(zhuǎn) 1 0 0 數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 void LeftBalance(BSTree amp。T){//右平衡化的算法 BSTree lc, rd。 lc=Trchild。 switch(lcbf){ case 1: Tbf = lcbf = 0。 L_Rotate(T)。 break。 case 1: rd=lclchild。 switch(rdbf){ case 1: Tbf=0。 lcbf=1。 break。 case 0: Tbf=lcbf=0。 break。 case 1: Tbf =1。 lcbf=0。 break。} rdbf=0。 R_Rotate(Tlchild)。 L_Rotate(T)。 } } 數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 例：按下述次序輸入關(guān)鍵字： e, i, p, k, m, l, b，試畫(huà)出AVL樹(shù)的構(gòu)造與調(diào)整過(guò)程。 eeipeiRR型 piekmLR型 miekplRL型 miekplbLL型 meikplb數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 B樹(shù)和 B+樹(shù) B樹(shù)是一種平衡的多路查找樹(shù)，它在文件系統(tǒng)中很有用，主要用作文件的索引，它的查找涉及外存的存取。 2 3 7 2 2 0 2 5F4 3 5 4 1 5 1 5 3F F F F F2 6 6 6 8F F F F F2 7 1 7 6 3 7 9 8 4 9 3F F F F F F F F F F2 1 2 3 0 2 6 9 7 81 5 4一 棵 5 階 的 B 樹(shù) ， 深 度 為 4abcd efgh it數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 （ 1） B樹(shù)的定義： 一棵 m階 的 B樹(shù)，或者為空樹(shù)，或?yàn)闈M足下列特性的 m叉樹(shù)： ① 樹(shù)中 每個(gè)結(jié)點(diǎn) 至多有 m棵 子樹(shù)； ② 若 根結(jié)點(diǎn) 不是葉子結(jié)點(diǎn)，則至少有 兩棵 子樹(shù)； ③ 除根結(jié)點(diǎn)之外的所有 非終端結(jié)點(diǎn)至少 有 ?m/2? 棵子樹(shù)； 2 3 7 2 2 0 2 5F4 3 5 4 1 5 1 5 3F F F F F2 6 6 6 8F F F F F2 7 1 7 6 3 7 9 8 4 9 3F F F F F F F F F F2 1 2 3 0 2 6 9 7 81 5 4一 棵 5 階 的 B 樹(shù) ， 深 度 為 4abcd efgh it數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 ④ 所有的非終端結(jié)點(diǎn) 中包含以下信息數(shù)據(jù)： (n, A0, K1, A1, K2, …, K n， An)。 其中： Ki（ i=1,2,…,n ） 為 關(guān)鍵字 ，且 KiKi+1。 Ai (i=0,1,…,n) 為指向子樹(shù)根結(jié)點(diǎn)的指針，且指針 Ai1 (i=1,2, …n 1)所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字 均大于 Ki，小于 Ki+1 ， A0所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字 均小于 K1， An所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字 均大于 Kn。 ?m/2? 1≤n≤m 1 ， n為 關(guān)鍵字的個(gè)數(shù) 。 2 3 7 2 2 0 2 5F4 3 5 4 1 5 1 5 3F F F F F2 6 6 6 8F F F F F2 7 1 7 6 3 7 9 8 4 9 3F F F F F F F F F F2 1 2 3 0 2 6 9 7 81 5 4一 棵 5 階 的 B 樹(shù) ， 深 度 為 4abcd efgh it數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 ⑤ 所有的葉子結(jié)點(diǎn) 都出現(xiàn)在同一層次上，并且不帶信息（可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針為空）。 2 3 7 2 2 0 2 5F4 3 5 4 1 5 1 5 3F F F F F2 6 6 6 8F F F F F2 7 1 7 6 3 7 9 8 4 9 3F F F F F F F F F F2 1 2 3 0 2 6 9 7 81 5 4一 棵 5 階 的 B 樹(shù) ， 深 度 為 4abcd efgh it數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 （ 2） B樹(shù)的查找： B樹(shù)的查找類(lèi)似 二叉排序樹(shù) 的查找，所不同的是 B樹(shù)每個(gè)結(jié)點(diǎn)上是 多關(guān)鍵字 的 有序表 。 若查找某個(gè)關(guān)鍵字，則在到達(dá)某個(gè)結(jié)點(diǎn)時(shí)，先在結(jié)點(diǎn)（ 有序表）中查找，若找到，則 查找成功 ；否則，到按照對(duì)應(yīng)的指針信息指向的子樹(shù)中去查找，當(dāng)?shù)竭_(dá)葉子結(jié)點(diǎn)時(shí)，則說(shuō)明樹(shù)中沒(méi)有對(duì)應(yīng)的關(guān)鍵字，查找失敗 。 即在 B樹(shù)上的查找過(guò)程是一個(gè) 順指針查找結(jié)點(diǎn) 和 在結(jié)點(diǎn)中查找關(guān)鍵字 交叉進(jìn)行的過(guò)程。 2 3 7 2 2 0 2 5F4 3 5 4 1 5 1 5 3F F F F F2 6 6 6 8F F F F F2 7 1 7 6 3 7 9 8 4 9 3F F F F F F F F F F2 1 2 3 0 2 6 9 7 81 5 4一 棵 5 階 的 B 樹(shù) ， 深 度 為 4abcd efgh it例如：查找關(guān)鍵字 41 數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 （ 3） B樹(shù)的查找分析： B樹(shù)的查找是由 兩個(gè)基本操作 交叉進(jìn)行的過(guò)程，即： ⑴在 B樹(shù)上找結(jié)點(diǎn)； ⑵在結(jié)點(diǎn)中找關(guān)鍵字。 由于 B樹(shù)通常是存儲(chǔ)在 外存 上的， 操作⑴ 是在磁盤(pán)上進(jìn)行的，就是通過(guò)指針在磁盤(pán)相對(duì)定位， 將結(jié)點(diǎn)信息讀入內(nèi)存 ； 操作 (2)是在內(nèi)存中進(jìn)行的，即 對(duì)結(jié)點(diǎn)中的關(guān)鍵字進(jìn)行順序查找或折半查找 。 因?yàn)?在磁盤(pán)上讀取結(jié)點(diǎn)信息 比 在內(nèi)存中進(jìn)行關(guān)鍵字查找 耗時(shí)多，所以，在磁盤(pán)上讀取結(jié)點(diǎn)信息的次數(shù)，即B樹(shù)的層次樹(shù) 是決定 B樹(shù)查找效率的 首要因素 。 數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 那么，對(duì)含有 n個(gè)關(guān)鍵字 的 m階 B樹(shù) ，最壞情況下達(dá)到多深呢？可按二叉平衡樹(shù)進(jìn)行類(lèi)似分析，討論 深度為 k+1的 m階 B樹(shù)所具有的 最少結(jié)點(diǎn)數(shù) 。 由 B樹(shù)定義： 第一層至少有 1個(gè)結(jié)點(diǎn)； 第二層至少有 2個(gè)結(jié)點(diǎn)； 由于除根結(jié)點(diǎn)外的每個(gè)非終端結(jié)點(diǎn) 至少有 ?m/2?棵子樹(shù) ，則第三層至少有 2(?m/2?)個(gè)結(jié)點(diǎn)； … 依此類(lèi)推，第 k+1層至少有 2(?m/2?)k1個(gè)結(jié)點(diǎn)。 而 k+1層的結(jié)點(diǎn)為 葉子結(jié)點(diǎn) 。若 m 階 B－樹(shù)有 n個(gè)關(guān)鍵字 ，則葉子結(jié)點(diǎn)即查找不成功的結(jié)點(diǎn)為 n+1(即 n個(gè)有序關(guān)鍵字形成的 n+1個(gè)中間區(qū)域 ) ； 由此可得 ? ? 1k)2m/(*21n ??? ? ? 1)2 1n(lo gk 2m/ ???即 ：在含有 n個(gè)關(guān)鍵字的 B樹(shù)上進(jìn)行查找時(shí)，從根結(jié)點(diǎn)到關(guān)鍵字所在結(jié)點(diǎn)的路徑上涉及的結(jié)點(diǎn)數(shù)不超過(guò) ? ? 12/1)(nlo g 2m/ ??數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 （ 4） B樹(shù)的插入： B樹(shù)的生成也是從 空樹(shù) 起，逐個(gè)插入關(guān)鍵字而得。在 B樹(shù)上插入關(guān)鍵字與在二叉排序樹(shù)上插入結(jié)點(diǎn)不同，關(guān)鍵字的插入不是在葉結(jié)點(diǎn)上進(jìn)行的，而是 在最底層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字 。 添加關(guān)鍵字分兩種情況： 1．若添加后， 結(jié)點(diǎn)上關(guān)鍵字個(gè)數(shù)小于等于 m1(對(duì)應(yīng)每個(gè)結(jié)點(diǎn)至多有 m棵子樹(shù)的限定條件 )，則插入結(jié)束； 4 53 7 5 03 1 2 6 1 7 0 1 0 02 4 5 3 9 0abec d fght一 棵 2 3 樹(shù)4 53 0 3 7 5 03 1 2 6 1 7 0 1 0 02 4 5 3 9 0abec d fght插 入 3 0 之 后數(shù)據(jù)結(jié)構(gòu) 第 9章 查找 2．若添加后， 該結(jié)點(diǎn)上關(guān)鍵字個(gè)數(shù)為 m個(gè) ，因而使該結(jié)點(diǎn)的子樹(shù) 超過(guò) 了m棵，這與 B樹(shù)定義不符，所以要進(jìn)行調(diào)整，即 結(jié)點(diǎn)的 “ 分裂 ” 。 結(jié)點(diǎn)的 “ 分裂 ” 方法 為：關(guān)鍵字加入結(jié)點(diǎn)后， 將結(jié)點(diǎn)中的關(guān)鍵字分成三部分 ，使得前后兩部分關(guān)鍵字個(gè)數(shù)均大于等于 ??m/2????，而中間部分只有一個(gè)結(jié)點(diǎn) (即第 ?m/2?個(gè)關(guān)鍵字 )。前后兩部分成為兩個(gè)結(jié)點(diǎn)，中間的一個(gè)結(jié)點(diǎn)將其插入到父結(jié)點(diǎn)中。 若插入父結(jié)點(diǎn)而使父結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)為 m個(gè)，則父結(jié)點(diǎn)繼續(xù)分裂，直到插入某個(gè)父結(jié)點(diǎn)，其關(guān)鍵字個(gè)數(shù)小于 m。 4 52 6 3 0 3 7 5 03 1 2 6 1 7 0 1 0 02