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