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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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