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