平衡二叉搜索樹(shù)(AVL)課件

1、數(shù) 據(jù) 結(jié) 構(gòu) DATA STRUCTURE, DS 平衡二叉搜索樹(shù)(AVL)數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容10.3.2 平衡二叉搜索樹(shù)(AVL) 二叉搜索樹(shù)BST受輸入順序影響最好O(log2n) 最壞O(n) 二叉搜索樹(shù)的改進(jìn)怎樣使得BST始終保持O(log2n)級(jí)的平衡狀態(tài)？Adelson-Velskii和Landis發(fā)明了AVL樹(shù)一種自平衡的二叉搜索樹(shù)任何結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的高度最多相差1AVL樹(shù)是對(duì)二叉搜索樹(shù)的操作規(guī)則做部分的改進(jìn)以使樹(shù)保持在一種類(lèi)似于平衡的狀態(tài)，從而達(dá)到較好的效率AVL樹(shù)的定義和性質(zhì)可以為空；如果T是一棵AVL樹(shù)，那么根結(jié)點(diǎn)的左右子樹(shù)TL、TR也是AVL樹(shù)；并且| hL-hR|

2、1 。其中h代表高度，hL、hR 是根的左右子樹(shù)的高度具有n個(gè)結(jié)點(diǎn)的AVL樹(shù)高度為O(log 2n) 。平衡因子(balance factor,bf)為方便起見(jiàn)，每個(gè)結(jié)點(diǎn)x增加數(shù)據(jù)域bf，表示結(jié)點(diǎn)x的平衡因子，定義為： AVL樹(shù)中任一個(gè)的結(jié)點(diǎn)的平衡因子可能取值為0，1和-1每插入或刪除結(jié)點(diǎn)要修改前驅(qū)結(jié)點(diǎn)的平衡因子例：判斷右側(cè)二叉樹(shù)是否是AVL樹(shù)？AVL樹(shù)結(jié)點(diǎn)的插入和平衡旋轉(zhuǎn) 插入與BST一樣新結(jié)點(diǎn)作葉結(jié)點(diǎn)，時(shí)間代價(jià)O(log2n)但有可能造成結(jié)構(gòu)失衡，此時(shí)需要自調(diào)整，使之恢復(fù)平衡，我們稱(chēng)調(diào)整的過(guò)程為重構(gòu)（restructuring）。調(diào)整方法是通過(guò)稱(chēng)為旋轉(zhuǎn)( rotation )的局部操作，這

3、種調(diào)整規(guī)則必須保持二叉搜索樹(shù)的中序遍歷順序旋轉(zhuǎn)可以歸納為四類(lèi)： LL型（單）旋轉(zhuǎn)( single rotation ) RR型（單）旋轉(zhuǎn) LR型（雙）旋轉(zhuǎn)( double rotation ) RL型（雙）旋轉(zhuǎn)若在結(jié)點(diǎn)(設(shè)A)的左子樹(shù)的根(設(shè)B)的左子樹(shù)上插入結(jié)點(diǎn)(設(shè)C)，使A的平衡因子從-1增加至-2，需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）ABCABC若在結(jié)點(diǎn)(設(shè)A)的右子樹(shù)的根(設(shè)B)的右子樹(shù)上插入結(jié)點(diǎn)(設(shè)C)，使A的平衡因子從1增加至2，需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）2）RR平衡旋轉(zhuǎn)：ABCABC1）LL平衡旋轉(zhuǎn)：這種調(diào)整規(guī)則可以保證二叉搜索樹(shù)的中序遍歷順序不變危急結(jié)點(diǎn)A左重

4、危急結(jié)點(diǎn)A右重若在結(jié)點(diǎn)(設(shè)A)的右子樹(shù)的根(設(shè)B)的左子樹(shù)上插入結(jié)點(diǎn)(設(shè)C)，使A的平衡因子從1增加至2，需要先進(jìn)行順時(shí)針旋轉(zhuǎn)，再逆時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）4）RL平衡旋轉(zhuǎn)：ABCABCABC若在結(jié)點(diǎn)(設(shè)A)的左子樹(shù)的根(設(shè)B)的右子樹(shù)上插入結(jié)點(diǎn)(設(shè)C)，使A的平衡因子從-1增加至-2，需要先進(jìn)行逆時(shí)針旋轉(zhuǎn)，再順時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）ABCABCABC3）LR平衡旋轉(zhuǎn)：危急結(jié)點(diǎn)A左重危急結(jié)點(diǎn)A右重這種調(diào)整規(guī)則可以保證二叉搜索樹(shù)的中序遍歷順序不變旋轉(zhuǎn)運(yùn)算的實(shí)質(zhì)把樹(shù)做任何一種旋轉(zhuǎn)（RR、RL、LL、LR）目的1：平衡保持插入前子樹(shù)的高度不變；原來(lái)二叉樹(shù)在A結(jié)點(diǎn)上面的其余部

5、分（若還有的話）總是保持平衡的。目的2：新樹(shù)保持了原來(lái)的中序遍歷順序旋轉(zhuǎn)的時(shí)間代價(jià)：O(1)處理中僅需改變少數(shù)指針插入單詞：cup ，cop， copy， hit， hi， his和 hia后得到的AVL樹(shù)1插入單詞：cup ，cop， copy， hit， hi， his和 hia后得到的AVL樹(shù) AVL樹(shù)結(jié)點(diǎn)的刪除 刪除是插入的逆操作。從刪除結(jié)點(diǎn)的意義上來(lái)說(shuō)，AVL樹(shù)的刪除操作與BST一樣，因此具體刪除過(guò)程可參考BST結(jié)點(diǎn)的刪除但是AVL樹(shù)的刪除比較復(fù)雜，因?yàn)橐３制胶庥捎谇闆r較多，列舉說(shuō)明AVL結(jié)點(diǎn)刪除后的調(diào)整刪除結(jié)點(diǎn)后AVL樹(shù)需要調(diào)整刪除結(jié)點(diǎn)可能導(dǎo)致子樹(shù)的高度以及平衡因子的變化，因此需

6、要調(diào)整此外，這個(gè)調(diào)整可能會(huì)導(dǎo)致被刪結(jié)點(diǎn)的祖先發(fā)生新的不平衡,，因此需要沿著被刪除結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑來(lái)調(diào)整這種變化調(diào)整策略從被刪除的結(jié)點(diǎn)開(kāi)始單旋轉(zhuǎn)或者雙旋轉(zhuǎn)操作 連續(xù)調(diào)整向上查找到其祖父結(jié)點(diǎn)，進(jìn)行單旋轉(zhuǎn)或者雙旋轉(zhuǎn)操作 這樣的調(diào)整操作要一直進(jìn)行下去，可能傳遞到根結(jié)點(diǎn)為止旋轉(zhuǎn)次數(shù)為O(log2n)，因此刪除結(jié)點(diǎn)的時(shí)間代價(jià)O(log2n)AVL樹(shù)刪除的例子AVL樹(shù)刪除的例子AVL樹(shù)刪除的例子衡AVL樹(shù)的效率 AVL樹(shù)的高度具有n個(gè)結(jié)點(diǎn)的AVL樹(shù)的高度一定是O(log2n)AVL樹(shù)的查找、插入和刪除效率都是O(1og2 n)，這是因?yàn)榫哂衝個(gè)結(jié)點(diǎn)的AVL樹(shù)的高度一定是O(log2n) AVL樹(shù)適用于組織

7、較小的、內(nèi)存中的目錄。而對(duì)于較大的、存放在外存儲(chǔ)器上的文件，用二叉搜索樹(shù)來(lái)組織索引就不合適了 在文件索引中大量使用每個(gè)結(jié)點(diǎn)包括多個(gè)關(guān)鍵字的B-樹(shù)，尤其是B+樹(shù) 10.3.3 B-樹(shù)（Balanced Tree）B-樹(shù)的特點(diǎn)它是一種平衡的多叉搜索樹(shù)是平衡二叉搜索樹(shù)的擴(kuò)展主要應(yīng)用于動(dòng)態(tài)查找B-樹(shù)的定義一棵m階B-樹(shù)，或者是一棵空樹(shù)，或者是滿足下列要求的m叉樹(shù)（階m可以事先任意指定，一旦指定后，就固定不變）：每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)；除根之外，其它每個(gè)非葉結(jié)點(diǎn)至少有 棵子樹(shù)；根至少有兩棵子樹(shù)(例外：根是葉結(jié)點(diǎn)時(shí)沒(méi)有子樹(shù))所有葉結(jié)點(diǎn)都在同一層上，不包含任何信息，可以看作是查找失敗或不存在的外部結(jié)點(diǎn)；每個(gè)

8、非葉結(jié)點(diǎn)的結(jié)構(gòu)為：n是結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)(非根結(jié)點(diǎn): ,根: )k1,k2,.,kn為n個(gè)從小到大排列的關(guān)鍵字，滿足kiki+1( )p0, pl, p2,., pn為(n+1)個(gè)指針，用于指向該結(jié)點(diǎn)的(n+l)棵子樹(shù)，且pi(i=1,2,n-1)所指向的子樹(shù)上的所有關(guān)鍵字均大于等于ki且小于ki+1 ， p0所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字均小于k1 ， pn所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字均大于kn。np0k1p1k2p2kipiknpn在 m (m3)階B-樹(shù)上，每個(gè)非葉子結(jié)點(diǎn)含有信息（n, p0, k1, p1, k2, p2, , kn, pn）： n 個(gè)關(guān)鍵字 ki（1 in）； n+1 個(gè)指

9、向子樹(shù)的指針 pi（0in）； 其中 m/2 -1 n m-1。m叉樹(shù)的特性非葉子結(jié)點(diǎn)中的多個(gè)關(guān)鍵字均自小至大有序排列，即：k1 k2 kn ； pi 所指子樹(shù)上所有關(guān)鍵字均小于ki+1； pi 所指子樹(shù)上所有關(guān)鍵字均大于等于ki 。搜索樹(shù)的特性平衡樹(shù)的特性所有葉結(jié)點(diǎn)均不帶信息，且在樹(shù)中的同一層次上；根結(jié)點(diǎn)：或?yàn)槿~結(jié)點(diǎn)；或至少有1個(gè)關(guān)鍵字和兩棵子樹(shù)，至多有m-1個(gè)關(guān)鍵字和m棵子樹(shù)；除根結(jié)點(diǎn)外的所有非葉子結(jié)點(diǎn)均：至少有m/2棵子樹(shù)，至多含有 m 棵子樹(shù)。B-樹(shù)的示例1，993，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第 1 層第 2 層第 3

10、 層第 4 層例如：m = 4 階 B- 樹(shù)。除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)至少為 = 2 個(gè)，至多為4 棵子樹(shù)（結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)至少為 1，至多為3 ）。該 B- 樹(shù)的深度為 4，葉子結(jié)點(diǎn)都在第 4 層上。 B-樹(shù)的查找算法查找關(guān)鍵字為key的記錄，從根結(jié)點(diǎn)開(kāi)始，將key與根結(jié)點(diǎn)中各個(gè)關(guān)鍵字k1,k2,kn進(jìn)行比較 (當(dāng)結(jié)點(diǎn)包含的關(guān)鍵字不多時(shí)，就用順序查找；當(dāng)結(jié)點(diǎn)包含的關(guān)鍵字?jǐn)?shù)目較多時(shí)，可用折半查找) ：若key=ki，查找成功；若keyk1，則沿p0所指的子樹(shù)繼續(xù)向下查找；若kikeykn，則沿pn所指的子樹(shù)繼續(xù)向下查找。如果找到了值為key的關(guān)鍵字，則查找成功；如果一直到葉

11、結(jié)點(diǎn)也未查到值為key的關(guān)鍵字，則查找失敗B-樹(shù)的查找示例1，993，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第 1 層第 2 層第 3 層(L層)第 4 層(L1層)例：在B-樹(shù)中分別查找key=58，key=28B-樹(shù)查找算法性能在B-樹(shù)上進(jìn)行查找需比較的結(jié)點(diǎn)數(shù)最多為B-樹(shù)的高度，B-樹(shù)的高度與B-樹(shù)的階m和關(guān)鍵字總數(shù)N有關(guān)。(1)若B-樹(shù)的高度為h+1，則h+1層(即葉結(jié)點(diǎn)所在的層)的結(jié)點(diǎn)數(shù)為N+1。因?yàn)槊總€(gè)非葉結(jié)點(diǎn)中的指針數(shù)等于其中的關(guān)鍵字?jǐn)?shù)加1，因此有： 結(jié)點(diǎn)總數(shù)=指針總數(shù)+1=(關(guān)鍵字總數(shù)N+非葉結(jié)點(diǎn)數(shù))+l (h+1)層的結(jié)點(diǎn)

12、數(shù)=葉結(jié)點(diǎn)數(shù)=結(jié)點(diǎn)總數(shù)非葉結(jié)點(diǎn)數(shù) =N+1。(2)根據(jù)B-樹(shù)的定義，B-樹(shù)的第一層(即根結(jié)點(diǎn))的結(jié)點(diǎn)數(shù)至少為1個(gè)，第二層的結(jié)點(diǎn)數(shù)至少為2，第三層的結(jié)點(diǎn)數(shù)至少為2m/2 ，第四層的結(jié)點(diǎn)數(shù)至少為2(m/2)2，以此類(lèi)推，第h+1層的結(jié)點(diǎn)數(shù)至少為2(m/2)h-1。(3)綜上所述，可得到如下不等式： h1+log m/2 (N+1)/2 B-樹(shù)的插入算法將key插入到m階B-樹(shù)中：找到關(guān)鍵字key應(yīng)插入的結(jié)點(diǎn)x（注意：插入結(jié)點(diǎn)一定是葉結(jié)點(diǎn)）；若x中關(guān)鍵字個(gè)數(shù)小于m-1，說(shuō)明其中有空位，將key直接插入合適位置即可；若x中關(guān)鍵字個(gè)數(shù)等于m-1，說(shuō)明x已滿，要插入key必須分裂x：將key插入x，再以中

13、間關(guān)鍵字為界將結(jié)點(diǎn)分為兩個(gè)結(jié)點(diǎn)，并把中間關(guān)鍵字向上插入到父結(jié)點(diǎn)中，若父結(jié)點(diǎn)也滿，繼續(xù)分裂，直至插入的結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)小于m-1。最壞的情況是一直分裂到根結(jié)點(diǎn)，這時(shí)樹(shù)的高度要加1。插入可能導(dǎo)致B-樹(shù)朝著根的方向生長(zhǎng)插入55，使得包含值50和52的結(jié)點(diǎn)分裂，把中間值52提升到父結(jié)點(diǎn) 階m=3，至少 1個(gè)關(guān)鍵字，至多2個(gè)關(guān)鍵字（至少2棵子樹(shù)，至多3棵子樹(shù)）插入55結(jié)果結(jié)點(diǎn)分裂插入引起3階B-樹(shù)根結(jié)點(diǎn)分裂的例子插入19（1）插入引起3階B-樹(shù)根結(jié)點(diǎn)分裂的例子插入19（2）插入19（3）插入19結(jié)果（4） B-樹(shù)的刪除（1）設(shè)m階B-樹(shù)，刪除其中某結(jié)點(diǎn)中的關(guān)鍵字key非葉結(jié)點(diǎn)關(guān)鍵字刪除可轉(zhuǎn)換為葉結(jié)點(diǎn)關(guān)鍵字

14、刪除該葉結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)大于m/21，直接刪去key ；該葉結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)等于 m/21，若其左（或右）兄弟結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)大于 m/21，則將左兄弟結(jié)點(diǎn)中最大的（或右兄弟結(jié)點(diǎn)中最小的）關(guān)鍵字上移到其雙親結(jié)點(diǎn)中，把雙親結(jié)點(diǎn)中大于（或小于）上移關(guān)鍵字的關(guān)鍵字下移到被刪關(guān)鍵字所在結(jié)點(diǎn)中（“借”）； B-樹(shù)的刪除（2）該葉結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)等于m/2 1，若其左（和右）兄弟結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)也等于m/2 1，需將被刪關(guān)鍵字所在結(jié)點(diǎn)與其左（或右）兄弟結(jié)點(diǎn)以及分割兩者的父結(jié)點(diǎn)中的那個(gè)關(guān)鍵字合并為一個(gè)結(jié)點(diǎn)；若導(dǎo)致父結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)小于m/2 1 ，按照上述方法繼續(xù)合并，直至所有結(jié)點(diǎn)滿足B-樹(shù)定義。最壞情

15、況一直到達(dá)根結(jié)點(diǎn)，可能將B-樹(shù)的高度-1 （“并”） B-樹(shù)的刪除示例3244553 90371005061，70被刪關(guān)鍵字503244561 90371005370借：向被刪結(jié)點(diǎn)方向旋轉(zhuǎn)假定再刪除關(guān)鍵字5332445 903710061，70假定再刪除關(guān)鍵字373，24 45 9010061，70并并3，2445 9010061，70并并：和父結(jié)點(diǎn)的一個(gè)關(guān)鍵字、及鄰居合并。有可能進(jìn)行到根，使B- 樹(shù)的深度降低一層！例如：3 階B-樹(shù)的刪除操作。m=3，m/2-1= 1；至少 1 個(gè)關(guān)鍵字，2個(gè)子結(jié)點(diǎn)。并：和父結(jié)點(diǎn)的一個(gè)關(guān)鍵字、及鄰居合并。10.3.4 B+樹(shù)背景當(dāng)數(shù)據(jù)量大，可采用索引方法實(shí)現(xiàn)

16、存儲(chǔ)和搜索，這樣只需從外存中讀索引表入內(nèi)存，搜索索引表后確定塊，再搜索塊后就可以完成搜索。當(dāng)數(shù)據(jù)量特別大時(shí)，索引表本身也很大，在內(nèi)存中放不下，需要分批多次讀取外存才能把索引表搜索一遍。在此情況下，可以建立索引的索引，稱(chēng)為二級(jí)索引。二級(jí)索引可以常駐內(nèi)存，二級(jí)索引中一個(gè)索引項(xiàng)對(duì)應(yīng)一個(gè)索引塊，登記該索引塊的最大關(guān)鍵碼及該索引塊的存儲(chǔ)地址。如果二級(jí)索引在內(nèi)存中也放不下，需要分為許多塊多次從外存讀入?？梢越⒍?jí)索引的索引，叫做三級(jí)索引。這時(shí)，訪問(wèn)外存次數(shù)等于讀入索引次數(shù)再加上1次讀取對(duì)象。必要的話，還可以有4級(jí)索引，5極索引，。B+樹(shù)示例：這種多級(jí)索引結(jié)構(gòu)形成一種 m 叉樹(shù)。樹(shù)中每一個(gè)分支結(jié)點(diǎn)表示一個(gè)

17、索引塊，它最多存放 m 個(gè)索引項(xiàng)，每個(gè)索引項(xiàng)分別給出各子樹(shù)結(jié)點(diǎn) (低一級(jí)索引塊) 的最大關(guān)鍵碼和結(jié)點(diǎn)地址。樹(shù)的葉結(jié)點(diǎn)中各索引項(xiàng)給出在數(shù)據(jù)表中存放的對(duì)象的關(guān)鍵碼和存放地址。這種m叉樹(shù)用來(lái)作為多級(jí)索引，就是m路搜索樹(shù)。m路搜索樹(shù)可能是靜態(tài)索引結(jié)構(gòu)，即結(jié)構(gòu)在初始創(chuàng)建，數(shù)據(jù)裝入時(shí)就已經(jīng)定型，在整個(gè)運(yùn)行期間，樹(shù)的結(jié)構(gòu)不發(fā)生變化。m路搜索樹(shù)還可能是動(dòng)態(tài)索引結(jié)構(gòu)，即在整個(gè)系統(tǒng)運(yùn)行期間，樹(shù)的結(jié)構(gòu)隨數(shù)據(jù)的增刪及時(shí)調(diào)整，以保持最佳的搜索效率。多級(jí)索引結(jié)構(gòu)形成m路搜索樹(shù)B+樹(shù)的特點(diǎn)是分塊查找思想的擴(kuò)展是多級(jí)索引結(jié)構(gòu)是B-樹(shù)的一種變形在葉結(jié)點(diǎn)上存儲(chǔ)信息的樹(shù)所有的關(guān)鍵字均出現(xiàn)在葉結(jié)點(diǎn)上 各層結(jié)點(diǎn)中的關(guān)鍵碼均是下一層相應(yīng)

18、結(jié)點(diǎn)中最大關(guān)鍵字（或最小關(guān)鍵字）的復(fù)寫(xiě)主要用于文件系統(tǒng) B+樹(shù)的結(jié)構(gòu)定義m階B+樹(shù)的結(jié)構(gòu)定義如下：(1)每個(gè)結(jié)點(diǎn)至多有m個(gè)子結(jié)點(diǎn)；(2)每個(gè)結(jié)點(diǎn)(除根外)至少有m/2個(gè)子結(jié)點(diǎn)；(3)根結(jié)點(diǎn)至少有兩個(gè)子結(jié)點(diǎn)；(4)有k個(gè)子結(jié)點(diǎn)的結(jié)點(diǎn)必有k個(gè)關(guān)鍵字；(5)所有的關(guān)鍵字均出現(xiàn)在葉結(jié)點(diǎn)上。 通常在B+樹(shù)上有兩個(gè)頭指針，一個(gè)指向根結(jié)點(diǎn)，另一個(gè)指向關(guān)鍵字最小的葉子結(jié)點(diǎn)，所有葉結(jié)點(diǎn)鏈接成一個(gè)不定長(zhǎng)的雙向鏈表。40 6535 4060 6555 6540 45 5520 25 3015 30 4010 15roothead3階B+樹(shù)的示例B+樹(shù)的查找在B+樹(shù)中可以采用兩種查找方式一種是直接從最小關(guān)鍵字開(kāi)始進(jìn)行順序查找（范圍查找） 另一種就是從B+樹(shù)的根結(jié)點(diǎn)開(kāi)始進(jìn)行隨機(jī)查找。這種查找方式與B-樹(shù)的查找方法相似，只是在分支結(jié)點(diǎn)上的關(guān)鍵字與查找值相等時(shí)，查找并不結(jié)束，要繼續(xù)查到葉結(jié)點(diǎn)為止，此時(shí)若查找成功，則按所給指針取出對(duì)應(yīng)記錄即可。因此，在B+樹(shù)中，不管查找成功與否，每次查找都是經(jīng)過(guò)了一條從樹(shù)根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑。B+樹(shù)的插入與B-樹(shù)的插入操作相似，B+樹(shù)的插入也從葉子結(jié)點(diǎn)開(kāi)始，當(dāng)插入后結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)大于