11 72 高度平衡二元树(cont).PPT

第七章 再論樹狀結構 目次 7.1 最佳的二元搜尋樹 7.2 高度平衡二元樹 7.3 2-3 Tree 7.4 2-3-4 Tree 7.1 最佳的二元搜尋樹 7.1.1 二元搜尋樹的效率分析 Ex：下圖皆為二元搜尋樹，但搜尋次數不太一樣 7.1 最佳的二元搜尋樹 平均而言 圖(a)搜尋Ralph的比較次數為一次；Isabelle與Ursula各二次；Devia為三次；Carman為四次。假使搜尋各鍵值的機率相等，則(a)的平均比較次數為 2.4次 圖(b)為2.2次 因此就平均而言，(b)的二元搜尋樹的效率還是比(a)好 7.1 最佳的二元搜尋樹(con.t) 延伸二元搜尋樹(extended binary search tree) 假使有一 n 個節點的二元樹，其必有 n+1 個空白的鏈結(link)，把這些空白鏈結所得到的節點以「外部節點」(external node)或稱「失敗節點」(failure node)型態表示 名詞定義 外徑長(E)：所有外部節點至樹根距離的總和 內徑長(I)：所有內部節點至樹根距離的總和 內徑長與外徑長的關係是 E = I + 2n (n為節點數) 7.1 最佳的二元搜尋樹(con.t) 下圖(a)、(b)皆為延伸二元搜尋樹，方塊表示外部節點，而圓圈表示內部節點 圖(a)的外徑長 E = (2+2+4+4+3+2) = 17， 內徑長 I = (1+3+2+1) = 7 內外徑長的關係 17 = 7 + 2*5 (得證) 7.1 最佳的二元搜尋樹(con.t) 加權外徑長的計算方式 Ex：下圖中左圖的加權外徑長為2*3+6*3+9*2+16*1=58 下圖中右圖的加權外徑長為2*2+6*2+9*2+16*2 = 66 7.1 最佳的二元搜尋樹(con.t) 求得最小的加權外徑長的方式(HUFFMAN) 先從串列中找尋兩個最小權數的節點(q1, q2) 接著將這兩個節點相結成一新的權數(q3)，並加入串列中 之後再從串列中挑選兩個最小權數的節點，並結合一新的權數，以此方式反覆進行…… Ex：假設目前有五個加權數，分別為q1 = 2, q2 = 4,q3 = 6, q4 = 7, q5 = 12及q6 = 15，過程如圖所示 7.1 最佳的二元搜尋樹(con.t) 7.2 高度平衡二元樹 何謂高度平衡二元樹(height balanced binary tree)？ 空樹(empty tree)是高度平衡二元樹 假使T不是空的二元樹，TL和TR分別是此二元樹的左子樹和右子樹，若符合下列二個條件，則稱T為高度平衡二元樹，也稱為AVL-Tree。 TL和TR亦是高度平衡二元樹， |hL-hR|≦1，其中hL及hR分別是TL和TR的高度； hL-hR為平衡因子(balanced factor，BF)，在AVL-Tree中，每一節點的平衡因子為-1、0或1 7.2 高度平衡二元樹(con.t) 一棵二元樹的平衡因子 7.2.1 高度平衡二元樹加入及其調整方式 四種調整方式： LL型：加入新節點於節點s的左子樹之左子樹 RR型：加入新節點於節點s的右子樹之右子樹 LR型：加入新節點於節點s的左子樹之右子樹 RL型：加入新節點於節點s的右子樹之左子樹 7.2.1 高度平衡二元樹加入及其調整方式(con.t) LL型：加入新節點於節點s的左子樹之左子樹 7.2.1 高度平衡二元樹加入及其調整方式(con.t) 再平衡 7.2.1 高度平衡二元樹加入及其調整方式(con.t) Ex：假設原來的AVL-tree 是空的 加入Mary，符合AVL-tree 的定義 加入May，符合AVL-tree 的定義 7.2.1 高度平衡二元樹加入及其調整方式(con.t) 加入Mike，不符合AVL-tree 的定義，利用RR的調整方式，使之再平衡 7.2.1 高度平衡二元樹加入及其調整方式(con.t) 加入Devin，符合AVL-tree 的定義 7.2.1 高度平衡二元樹加入及其調整方式(con.t) 加入Bob，不符合AVL-tree 的定義，利用LL的調整方式，使之再平衡 7.2.1 高度平衡二元樹加入及其調整方式(con.t) 加入Jack，不符合AVL-tree 的定義，利用LR的調整方式，使之再平衡 7.2.2 高度平衡二元樹刪除及其調整方式 假設存在一棵AVL-tree如右： 如欲刪除樹葉節點 50，則結果如下所示，但刪除並不符合AVL-tree的定義，利用LL的調整方式使之再平衡 7.2.2 高度平衡二元樹刪除及其調整方式(con.t) 刪除非樹葉節點 有