數(shù)據(jù)結(jié)構(gòu)教程第3版四ppt(編輯修改稿)

　

【文章內(nèi)容簡(jiǎn)介】 ,通過(guò)平衡因子 (balancd factor,用 bf表示 )來(lái)具體實(shí)現(xiàn)上述平衡二叉樹(shù)的定義 。 平衡因子的定義是：平衡二叉樹(shù)中每個(gè)結(jié)點(diǎn)有一個(gè)平衡因子域 ,每個(gè)結(jié)點(diǎn)的平衡因子是該結(jié)點(diǎn)左子樹(shù)的高度減去右子樹(shù)的高度 。 從平衡因子的角度可以說(shuō) ,若一棵二叉樹(shù)中所有結(jié)點(diǎn)的平衡因子的絕對(duì)值小于或等于 1,即平衡因子取值為 0或 1,則該二叉樹(shù)稱為平衡二叉樹(shù) 。 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 平衡二叉樹(shù)和不平衡二叉樹(shù) 定義 AVL樹(shù)的結(jié)點(diǎn)的類型如下： typedef struct node /*記錄類型 */ { KeyType key。 /*關(guān)鍵字項(xiàng) */ int bf。 /*增加的平衡因子 */ InfoType data。 /*其他數(shù)據(jù)域 */ struct node *lchild,*rchild。 /*左右孩子指針 */ } BSTNode。 假定向平衡二叉樹(shù)中插入一個(gè)新結(jié)點(diǎn)后破壞了平衡二叉樹(shù)的平衡性 ,首先要找出插入新結(jié)點(diǎn)后失去平衡的最小子樹(shù)根結(jié)點(diǎn)的指針 ,然后再調(diào)整這個(gè)子樹(shù)中有關(guān)結(jié)點(diǎn)之間的鏈接關(guān)系 ,使之成為新的平衡子樹(shù) 。 當(dāng)失去平衡的最小子樹(shù)被調(diào)整為平衡子樹(shù)后 ,原有其他所有不平衡子樹(shù)無(wú)需調(diào)整 ,整個(gè)二叉排序樹(shù)就又成為一棵平衡二叉樹(shù) 。 失去平衡的最小子樹(shù)是指以離插入結(jié)點(diǎn)最近 ,且平衡因子絕對(duì)值大于 1的結(jié)點(diǎn)作為根的子樹(shù) 。 假設(shè)用 A表示失去平衡的最小子樹(shù)的根結(jié)點(diǎn) ,則調(diào)整該子樹(shù)的操作可歸納為下列四種情況： (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樹(shù)的步驟 。 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)整 在平衡二叉樹(shù)上進(jìn)行查找的過(guò)程和在二叉排序樹(shù)上進(jìn)行查找的過(guò)程完全相同 ， 因此 ， 在平衡二叉樹(shù)上進(jìn)行查找關(guān)鍵字的比較次數(shù)不會(huì)超過(guò)平衡二叉樹(shù)的深度 。 在最壞的情況下 ， 普通二叉排序樹(shù)的查找長(zhǎng)度為O(n)。 那么 ， 平衡二叉樹(shù)的情況又是怎樣的呢 ？ 下面分析平衡二叉樹(shù)的高度 h和結(jié)點(diǎn)個(gè)數(shù) n之間的關(guān)系 。 首先 ， 構(gòu)造一系列的平衡二叉樹(shù) T1 ， T2 ，T3， … ， 其中 ， Th（ h=1， 2， 3， … ） 是高度為 h且結(jié)點(diǎn)數(shù)盡可能少的平衡二叉樹(shù) ， 如圖 T1， T2， T3和 T4。 為了構(gòu)造 Th， 先分別構(gòu)造 Th1和 Th2， 使 Th以 Th1和 Th2作為其根結(jié)點(diǎn)的左 、 右子樹(shù) 。 對(duì)于每一個(gè) Th， 只要從中刪去一個(gè)結(jié)點(diǎn) ， 就會(huì)失去平衡或高度不再是 h（ 顯然 ， 這樣構(gòu)造的平衡二叉樹(shù)在結(jié)點(diǎn)個(gè)數(shù)相同的平衡二叉樹(shù)中具有最大高度 ） 。 T 1 T 2 T 3 T 4 T h T h 1 T h 2 圖 結(jié)點(diǎn)個(gè)數(shù) n最少的平衡二叉樹(shù) 然后 ， 通過(guò)計(jì)算上述平衡二叉樹(shù)中的結(jié)點(diǎn)個(gè)數(shù) ， 來(lái)建立高度 與結(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) 通過(guò)檢查兩個(gè)序列的前幾項(xiàng)就可發(fā)現(xiàn)兩者之間的對(duì)應(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)的平衡二叉樹(shù)的平均查找長(zhǎng)度為 O(log2n)。 ?h51251???12151 2 ???? hh? B樹(shù) B樹(shù)又稱為多路平衡查找樹(shù) ,是一種組織和維護(hù)外存文件系統(tǒng)非常有效的數(shù)據(jù)結(jié)構(gòu) 。 B樹(shù)中所有結(jié)點(diǎn)的孩子結(jié)點(diǎn)最大值稱為 B樹(shù)的階 ,通常用 m表示 ,從查找效率考慮 ,要求 m≥3。 一棵 m階 B樹(shù)或者是一棵空樹(shù) ,或者是滿足下列要求的 m叉樹(shù)： (1) 樹(shù)中每個(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樹(shù)是所有結(jié)點(diǎn)的平衡因子均等于 0的多路查找樹(shù) 。 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樹(shù) 在 B樹(shù)的存儲(chǔ)結(jié)構(gòu)中 ,各結(jié)點(diǎn)的類型定義如下： define MAXM 10 /*定義 B樹(shù)的最大的階數(shù) */ typedef int KeyType。 /*KeyType為關(guān)鍵字類型 */ typedef struct node /*B樹(shù)結(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樹(shù)的查找 在 B樹(shù)中查找給定關(guān)鍵字的方法類似于二叉排序樹(shù)上的查找 ,不同的是在每個(gè)記錄上確定向下查找的路徑不一定是二路 (即二叉 )的 ,而是 n+1路的 。 因?yàn)橛涗泝?nèi)的關(guān)鍵字序列是有序的數(shù)量 key[1..n],故既可以用順序查找 ,也可以用折半查找 。 在一棵 B樹(shù)上順序查找關(guān)鍵字為 k的方法為： 將 k與根結(jié)點(diǎn)中的 key[i]進(jìn)行比較： (1) 若 k=key[i],則查找成功； (2) 若 k＜ key[1],則沿著指針 ptr[0]所指的子樹(shù)繼續(xù)查找； (3) 若 key[i]＜ k＜ key[i+1],則沿著指針 ptr[i]所指的子樹(shù)繼續(xù)查找； (4) 若 k＞ key[n],則沿著指針 ptr[n]所指的子樹(shù)繼續(xù)查找 。 2. B樹(shù)的插入 將關(guān)鍵字 k插入到 B樹(shù)的過(guò)程分兩步完成： (1) 利用前述的 B樹(shù)的查找算法找出該關(guān)鍵字的插入結(jié)點(diǎn) (注意 B樹(shù)的插入結(jié)點(diǎn)一定是葉子結(jié)點(diǎn) )。 (2) 判斷該結(jié)點(diǎn)是否還有空位置 ,即判斷該結(jié)點(diǎn)是否滿足 n＜ m1,若該結(jié)點(diǎn)滿足 n＜ m1,說(shuō)明該結(jié)點(diǎn)還有空位置 ,直接把關(guān)鍵字 k插入到該結(jié)點(diǎn)的合適位置上 (即滿足插入后結(jié)點(diǎn)上的關(guān)鍵字仍保持有序 )； 若該結(jié)點(diǎn)有 n=m1,說(shuō)明該結(jié)點(diǎn)已沒(méi)有空位置 ,需要把結(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)的存儲(chǔ)位置插入到父親結(jié)點(diǎn)中 。 如果父結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)也超過(guò) Max,則要再分裂 ,再往上插 ,直至這個(gè)過(guò)程傳到根結(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樹(shù) 。 建立 B的過(guò)程如下圖所示 。 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樹(shù)的刪除 B樹(shù)的刪除過(guò)程與插入過(guò)程類似 ,只是稍為復(fù)雜一些 。要使刪除后的結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù) ≥?m/2?1,將涉及到結(jié)點(diǎn)的 “ 合并 ” 問(wèn)題 。 在 B樹(shù)上刪除關(guān)鍵字 k的過(guò)程分兩步完成：