【文章內(nèi)容簡介】 ,通過平衡因子 (balancd factor,用 bf表示 )來具體實(shí)現(xiàn)上述平衡二叉樹的定義 。 平衡因子的定義是：平衡二叉樹中每個(gè)結(jié)點(diǎn)有一個(gè)平衡因子域 ,每個(gè)結(jié)點(diǎn)的平衡因子是該結(jié)點(diǎn)左子樹的高度減去右子樹的高度 。 從平衡因子的角度可以說 ,若一棵二叉樹中所有結(jié)點(diǎn)的平衡因子的絕對值小于或等于 1,即平衡因子取值為 0或 1,則該二叉樹稱為平衡二叉樹 。 5 2 6 1 4 3 7 1 0 1 0 1 0 1 3 1 4 2 5 6 7 (b ) (a) 0 1 2 3 2 1 0 平衡二叉樹和不平衡二叉樹 定義 AVL樹的結(jié)點(diǎn)的類型如下： typedef struct node /*記錄類型 */ { KeyType key。 /*關(guān)鍵字項(xiàng) */ int bf。 /*增加的平衡因子 */ InfoType data。 /*其他數(shù)據(jù)域 */ struct node *lchild,*rchild。 /*左右孩子指針 */ } BSTNode。 假定向平衡二叉樹中插入一個(gè)新結(jié)點(diǎn)后破壞了平衡二叉樹的平衡性 ,首先要找出插入新結(jié)點(diǎn)后失去平衡的最小子樹根結(jié)點(diǎn)的指針 ,然后再調(diào)整這個(gè)子樹中有關(guān)結(jié)點(diǎn)之間的鏈接關(guān)系 ,使之成為新的平衡子樹 。 當(dāng)失去平衡的最小子樹被調(diào)整為平衡子樹后 ,原有其他所有不平衡子樹無需調(diào)整 ,整個(gè)二叉排序樹就又成為一棵平衡二叉樹 。 失去平衡的最小子樹是指以離插入結(jié)點(diǎn)最近 ,且平衡因子絕對值大于 1的結(jié)點(diǎn)作為根的子樹 。 假設(shè)用 A表示失去平衡的最小子樹的根結(jié)點(diǎn) ,則調(diào)整該子樹的操作可歸納為下列四種情況： (1) LL型調(diào)整 (2) RR型調(diào)整 (3) LR型調(diào)整 (4) RL型調(diào)整 例 輸入關(guān)鍵字序列 {16,3,7,11,9,26,18,14,15},給出構(gòu)造一棵 AVL樹的步驟 。 16 0 ( a) 插入 16 16 1 ( b ) 插入 3 3 0 16 2 ( c ) 插入 7 3 1 7 0 7 0 (d )LR 調(diào)整 3 0 16 0 7 1 ( e ) 插入 11 3 0 16 1 11 0 7 2 ( f ) 插入 9 3 0 16 2 11 1 9 0 7 1 ( g ) LL 調(diào)整 3 0 1 1 0 9 0 16 0 7 2 3 0 1 1 1 9 0 16 1 ( h ) 插入 26 26 0 7 0 3 0 1 1 0 9 0 16 1 26 0 ( i ) RR 調(diào)整 7 0 3 0 1 1 1 9 0 16 2 26 1 ( j ) 插入 18 18 0 7 0 3 0 1 1 0 9 0 18 0 26 0 ( k ) RL 調(diào)整 16 0 7 0 3 0 1 1 1 9 0 18 1 26 0 16 1 ( l ) 插入 14 14 0 7 0 3 0 1 1 2 9 0 18 2 26 0 16 2 ( m ) 插入 15 14 1 15 0 7 0 3 0 1 1 1 9 0 18 1 26 0 15 0 0 14 16 0 ( n ) L R 調(diào)整 在平衡二叉樹上進(jìn)行查找的過程和在二叉排序樹上進(jìn)行查找的過程完全相同 ， 因此 ， 在平衡二叉樹上進(jìn)行查找關(guān)鍵字的比較次數(shù)不會超過平衡二叉樹的深度 。 在最壞的情況下 ， 普通二叉排序樹的查找長度為O(n)。 那么 ， 平衡二叉樹的情況又是怎樣的呢 ？ 下面分析平衡二叉樹的高度 h和結(jié)點(diǎn)個(gè)數(shù) n之間的關(guān)系 。 首先 ， 構(gòu)造一系列的平衡二叉樹 T1 ， T2 ，T3， … ， 其中 ， Th（ h=1， 2， 3， … ） 是高度為 h且結(jié)點(diǎn)數(shù)盡可能少的平衡二叉樹 ， 如圖 T1， T2， T3和 T4。 為了構(gòu)造 Th， 先分別構(gòu)造 Th1和 Th2， 使 Th以 Th1和 Th2作為其根結(jié)點(diǎn)的左 、 右子樹 。 對于每一個(gè) Th， 只要從中刪去一個(gè)結(jié)點(diǎn) ， 就會失去平衡或高度不再是 h（ 顯然 ， 這樣構(gòu)造的平衡二叉樹在結(jié)點(diǎn)個(gè)數(shù)相同的平衡二叉樹中具有最大高度 ） 。 T 1 T 2 T 3 T 4 T h T h 1 T h 2 圖 結(jié)點(diǎn)個(gè)數(shù) n最少的平衡二叉樹 然后 ， 通過計(jì)算上述平衡二叉樹中的結(jié)點(diǎn)個(gè)數(shù) ， 來建立高度 與結(jié)點(diǎn)個(gè)數(shù)之間的關(guān)系 。 設(shè) N(h)為 Th的結(jié)點(diǎn)數(shù) ， 從圖 可以看出有下列關(guān)系成立： N(1)=1， N(2)=2， N(h)=N(h1)+N(h2)+1 當(dāng) h1時(shí) ， 此關(guān)系類似于定義 Fibonacci數(shù)的關(guān)系： F(1)=1， F(2)=1， F(h)=F(h1)+F(h2) 通過檢查兩個(gè)序列的前幾項(xiàng)就可發(fā)現(xiàn)兩者之間的對應(yīng)關(guān)系： N(h)=F(h+2)1 由于 Fibonacci數(shù)滿足漸近公式： F(h)= 其中 ， 故由此可得近似公式： N(h)= 即： h≈log2(N(h)+1) 所以 ， 含有 n個(gè)結(jié)點(diǎn)的平衡二叉樹的平均查找長度為 O(log2n)。 ?h51251???12151 2 ???? hh? B樹 B樹又稱為多路平衡查找樹 ,是一種組織和維護(hù)外存文件系統(tǒng)非常有效的數(shù)據(jù)結(jié)構(gòu) 。 B樹中所有結(jié)點(diǎn)的孩子結(jié)點(diǎn)最大值稱為 B樹的階 ,通常用 m表示 ,從查找效率考慮 ,要求 m≥3。 一棵 m階 B樹或者是一棵空樹 ,或者是滿足下列要求的 m叉樹： (1) 樹中每個(gè)結(jié)點(diǎn)至多有 m個(gè)孩子結(jié)點(diǎn) (即至多有 m1個(gè)關(guān)鍵字 )； (2) 除根結(jié)點(diǎn)外 ,其他結(jié)點(diǎn)至少有 ?m/2?個(gè)孩子結(jié)點(diǎn)(即至少有 ?m/2?1=?(m1)/2?個(gè)關(guān)鍵字 )； (3) 若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn) ,則根結(jié)點(diǎn)至少有兩個(gè)孩子結(jié)點(diǎn) ； (4) 每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為： n p0 k1 p1 k2 p2 … kn pn 其中 ,n為該結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù) ,除根結(jié)點(diǎn)外 ,其他所有結(jié)點(diǎn)的 n大于等于 ?m/2?1,且小于等于 m1；ki(1≤i≤n)為 該 結(jié)點(diǎn) 的 關(guān)鍵 字 且滿 足 ki ＜ ki+1 ；pi(0≤i≤n)為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)指針且滿足 pi(0≤i≤n1)結(jié)點(diǎn)上的關(guān)鍵字大于等于 ki且小于 ki+1,pn結(jié)點(diǎn)上的關(guān)鍵字大于 kn。 (5) 所有葉子結(jié)點(diǎn)都在同一層上 ,即 B樹是所有結(jié)點(diǎn)的平衡因子均等于 0的多路查找樹 。 3 ∧ 12 ∧ 15 ∧ 22 ∧ 2 ∧ 2 ∧ 7 ∧ 2 ∧ 35 ∧ 41 ∧ 3 ∧ 53 ∧ 54 ∧ 63 ∧ 4 ∧ 68 ∧ 69 ∧ 71 ∧ 76 ∧ 3 ∧ 79 ∧ 84 ∧ 93 ∧ 2 ? 11 ? 30 ? 2 ? 66 ? 78 ? 1 ? 51 ? 一棵 5階 B樹 在 B樹的存儲結(jié)構(gòu)中 ,各結(jié)點(diǎn)的類型定義如下： define MAXM 10 /*定義 B樹的最大的階數(shù) */ typedef int KeyType。 /*KeyType為關(guān)鍵字類型 */ typedef struct node /*B樹結(jié)點(diǎn)類型定義 */ { int keynum。 /*結(jié)點(diǎn)當(dāng)前擁有的關(guān)鍵字的個(gè)數(shù) */ KeyType key[MAXM]。 /*[1..keynum]存放關(guān)鍵字 ,[0]不用 */ struct node *parent。 /*雙親結(jié)點(diǎn)指針 */ struct node *ptr[MAXM]。/*孩子結(jié)點(diǎn)指針數(shù)組 [0..keynum]*/ } BTNode。 1. B樹的查找 在 B樹中查找給定關(guān)鍵字的方法類似于二叉排序樹上的查找 ,不同的是在每個(gè)記錄上確定向下查找的路徑不一定是二路 (即二叉 )的 ,而是 n+1路的 。 因?yàn)橛涗泝?nèi)的關(guān)鍵字序列是有序的數(shù)量 key[1..n],故既可以用順序查找 ,也可以用折半查找 。 在一棵 B樹上順序查找關(guān)鍵字為 k的方法為： 將 k與根結(jié)點(diǎn)中的 key[i]進(jìn)行比較： (1) 若 k=key[i],則查找成功； (2) 若 k＜ key[1],則沿著指針 ptr[0]所指的子樹繼續(xù)查找； (3) 若 key[i]＜ k＜ key[i+1],則沿著指針 ptr[i]所指的子樹繼續(xù)查找； (4) 若 k＞ key[n],則沿著指針 ptr[n]所指的子樹繼續(xù)查找 。 2. B樹的插入 將關(guān)鍵字 k插入到 B樹的過程分兩步完成： (1) 利用前述的 B樹的查找算法找出該關(guān)鍵字的插入結(jié)點(diǎn) (注意 B樹的插入結(jié)點(diǎn)一定是葉子結(jié)點(diǎn) )。 (2) 判斷該結(jié)點(diǎn)是否還有空位置 ,即判斷該結(jié)點(diǎn)是否滿足 n＜ m1,若該結(jié)點(diǎn)滿足 n＜ m1,說明該結(jié)點(diǎn)還有空位置 ,直接把關(guān)鍵字 k插入到該結(jié)點(diǎn)的合適位置上 (即滿足插入后結(jié)點(diǎn)上的關(guān)鍵字仍保持有序 )； 若該結(jié)點(diǎn)有 n=m1,說明該結(jié)點(diǎn)已沒有空位置 ,需要把結(jié)點(diǎn)分裂成兩個(gè) 。 分裂的做法是 ,取一新結(jié)點(diǎn) ,把原結(jié)點(diǎn)上的關(guān)鍵字和 k按升序排序后 ,從中間位置 (即 ?m/2?=?(m+1)/2?之處 )把關(guān)鍵字 (不包括中間位置的關(guān)鍵字 )分成兩部分 ,左部分所含關(guān)鍵字放在舊結(jié)點(diǎn)中 ,右部分所含關(guān)鍵字放在新結(jié)點(diǎn)中 ,中間位置的關(guān)鍵字連同新結(jié)點(diǎn)的存儲位置插入到父親結(jié)點(diǎn)中 。 如果父結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)也超過 Max,則要再分裂 ,再往上插 ,直至這個(gè)過程傳到根結(jié)點(diǎn)為止 。 例如 關(guān)鍵字序列為： {1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15} 。 創(chuàng)建一棵 5階 B樹 。 建立 B的過程如下圖所示 。 1 2 6 7 6 1 2 7 1 1 6 1 2 4 7 8 1 1 1 3 6 1 0 1 2 4 1 1 1 3 7 8 6 1 0 1 2 4 5 1 1 1 3 1 6 17 7 8 9 6 1 0 1 6 1 2 4 5 7 8 9 3 6 1 0 16 1 2 7 8 9 1 7 1 8 1 9 2 0 4 5 10 1 4 1 5 1 3 1 6 3 6 1 2 7 8 9 (a) 插入 1 , 2 , 6 , 7 (b ) 插入 11 (c) 插入 4 , 8 , 1 3 (d ) 插入 10 (e) 插入 5 , 1 7 , 9 , 1 6 (f) 插入 20 (g ) 插入 3 , 1 2 , 1 4 , 1 8 , 1 9 (h ) 插入 15 1 1 1 3 1 7 2 0 1 7 1 8 1 9 2 0 1 1 1 2 1 3 1 4 4 5 1 1 1 2 3. B樹的刪除 B樹的刪除過程與插入過程類似 ,只是稍為復(fù)雜一些 。要使刪除后的結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù) ≥?m/2?1,將涉及到結(jié)點(diǎn)的 “ 合并 ” 問題 。 在 B樹上刪除關(guān)鍵字 k的過程分兩步完成：