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

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

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

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

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

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

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

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

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

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

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

11、結點也未查到值為key的關鍵字，則查找失敗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-樹上進行查找需比較的結點數(shù)最多為B-樹的高度，B-樹的高度與B-樹的階m和關鍵字總數(shù)N有關。(1)若B-樹的高度為h+1，則h+1層(即葉結點所在的層)的結點數(shù)為N+1。因為每個非葉結點中的指針數(shù)等于其中的關鍵字數(shù)加1，因此有： 結點總數(shù)=指針總數(shù)+1=(關鍵字總數(shù)N+非葉結點數(shù))+l (h+1)層的結點

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

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

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

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

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

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

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