Chapter 9 高度平衡二元搜尋樹 AVL Binary Search Tree

Presentation on theme: "Chapter 9 高度平衡二元搜尋樹 AVL Binary Search Tree"— Presentation transcript:

1 Chapter 9 高度平衡二元搜尋樹 AVL Binary Search Tree

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

3 高度平衡二元樹 一棵二元樹的平衡因子 hL(M)=0, hR(M)=2 hL-hR=-2 Q BF= –2 M S BF=1 P R
N

4 高度平衡二元樹加入及其調整方式 利用加入的節點A與它最接近平衡因子絕對值大於1(|BF|>1)的節點B
高度平衡二元樹可能會因為加入或刪除某節點而造成不平衡，此時必須利用四種不同的調整方式來重建一棵AVL-tree使其平衡。 四種調整方式： LL型：加入新節點於節點s的左子樹之左子樹 RR型：加入新節點於節點s的右子樹之右子樹 LR型：加入新節點於節點s的左子樹之右子樹 RL型：加入新節點於節點s的右子樹之左子樹

5 高度平衡二元樹加入及其調整方式 原則: 先找到最接近新節點之平衡因子絕對值大於1(|BF|>1)的祖先節點
將其高度降低使其符合AVL的定義 LL 往右旋轉(rotate) RR 往左旋轉 LR 先右後左 RL 先左後右

6 高度平衡二元樹加入及其調整方式 LL型：加入新節點於節點s的左子樹之左子樹 加入30 調整 不是一棵AVL-tree 2 50 50 40
50 50 40 加入30 調整 1 40 40 30 50 不是一棵AVL-tree 30

7 高度平衡二元樹加入及其調整方式 例二： 加入20 調整 1 2 50 50 40 1 1 40 60 40 60 30 50 1 30 45
1 2 50 50 40 1 1 加入20 調整 40 60 40 60 30 50 1 30 45 30 45 20 45 60 20

8 高度平衡二元樹加入及其調整方式 RR型：加入新節點於節點s的右子樹之右子樹 此RR型與LL型大同小異，如加入前的AVL-tree為：
-2 加入70 調整 60 50 50 -1 50 70 60 60 70 不是一棵AVL-tree

9 高度平衡二元樹加入及其調整方式 例二： 加入80 調整 -1 -2 50 50 60 -1 -1 40 60 40 60 50 70 -1
-1 -2 50 50 60 加入80 調整 -1 -1 40 60 40 60 50 70 -1 55 70 55 70 40 55 80 80

10 高度平衡二元樹加入及其調整方式 LR型：加入新節點於節點s的左子樹之右子樹 加入45 調整 2 50 50 45 -1 40 40 40
45

11 高度平衡二元樹加入及其調整方式 例二： 2 50 50 -1 加入42 40 60 40 60 1 30 45 30 45 42

12 高度平衡二元樹加入及其調整方式 45 調整 40 50 30 42 60

13 高度平衡二元樹加入及其調整方式 RL型：加入新節點於節點s的右子樹之左子樹 加入56 調整 -2 50 50 56 1 60 60 50
56

14 高度平衡二元樹加入及其調整方式 例二： 加入52 調整 -1 -2 50 50 56 1 40 60 40 60 50 60 1 56 70
1 40 60 40 60 50 60 1 56 70 56 70 40 52 70 52

15 高度平衡二元樹刪除及其調整方式 AVL-tree的刪除與二元搜尋樹的刪除相同，當刪除的動作完成後，再計算平衡因子，作適當的調整，直到平衡因子的絕對值皆小於等於1。

16 高度平衡二元樹刪除及其調整方式 假設存在一棵AVL-tree如左下圖，若欲刪除50，因為它為一樹葉節點，故直接刪除之，成為右下圖，刪除後再進行調整 2 -1 刪除50 調整 30 30 20 1 20 50 20 10 30 10 25 10 25 25

17 高度平衡二元樹刪除及其調整方式 從樹根尋找pivot點（遇到第一個BF值的絕對值大於1的節點）

18 高度平衡二元樹刪除及其調整方式 調整規則如下： 當pivotBF > 0 當pivotBF < 0
pivotllinkBF >= 0 LL型 pivotllinkBF <= 0 LR型 當pivotBF < 0 pivotrlinkBF >= 0 RL型 pivotrlinkBF <= 0 RR型

19 運作 陣列 鏈結串列 高度平衡 二元樹 搜尋 O(log n) O(n) 插入 O(1) 刪除