AVL

Report
高度平衡二元搜尋樹
學號:96363034
姓名:胡容豪
何謂高度平衡二元搜尋樹
2
1.
1962年,兩位蘇聯數學家,G.M.AdelsonVelskii與E.M.Landis建立這個平衡的二元樹結
構。
2.
樹的取名,就是依據他們的名字─AVL樹。
3.
AVL樹就是子樹的高度差不超過1的搜尋樹。
兩棵二元搜尋樹
3
建立下列數字之二元搜尋樹
1.


依序 8,12,14,18,20,23,44,52
依序 23,18,12,8,14,20,44,52
兩棵二元搜尋樹
4
依序 8,12,14,18,20,23,44,52
依序 23,18,12,8,14,20,44,52
(b )
(a ) 一 個 不 平 衡 的
BST
一 個
AVL 樹
何謂高度平衡二元搜尋樹
5
一棵空樹(empty tree)是高度平二元搜尋樹。
假使T不是空的二元搜尋樹,TL和TR分別是此二
元搜尋樹的左子樹和右子樹,若符合下列兩個
條件,則稱T為高度平衡二元搜尋樹:(1)TL和TR
亦是高度平衡二元搜尋樹。
(2)|hL-hR| ≤ 1,其中hL及hR分別是TL和TR的高度。
何謂高度平衡二元搜尋樹
6
在一棵二元搜尋樹中有一節點p,其左子樹 (TL)
和右子樹 (TR) 的高度分別是hL和hR,而BF(p)表
示p節點的平衡因子(balanced factor)。平衡
因子之計算為hL-hR。在一棵AVL-tree裡,每一
節點的平衡因子為-1或零或1,即 |BF(p) | ≤
1。
一棵AVL樹
7
( a ) 子 樹 2 3 是 平 衡 的 :H L - H R = 1
( c ) 子 樹 4 4 是 平 衡 的 :| H L - H R |= 1
( b ) 子 樹 1 8 是 平 衡 的 : H L-H A = 1
AVL-tree的加入
8
1.
2.
高度平衡二元搜尋樹可能會因為加入或刪除某節
點而形成不平衡狀態,此時須視不平衡狀態是那
一類型,之後,再加以調整之。
通常不平衡的狀態可分為LL、RR、LR與RL四大類
型。
AVL-tree的加入
9
利用加入的節點A與它最接近平衡因子絕對值大於
1(|BF|>1)的節點B:
1.
2.
3.
4.
若A在B節點的左邊的左邊,則為LL型。
若A在B節點的右邊的右邊,則為RR型。
若A在B節點的左邊的右邊,則為LR型。
若A在B節點的右邊的左邊,則為RL型。
AVL 樹的不平衡點調整之四種型式
10
(1)LL型
(2)RR型
(3)LR型
(4)RL型
AVL 樹之平衡調整步驟
11
1.
2.
3.
4.
找出關鍵路徑,計算路徑上每一節點的平衡因
子。
從樹根開始,找到最後一個平衡因子大於1以上
的節點,稱為關鍵節點。
決定調整種類(LL、RR、RL、LR)。
進行調整,必須保持二元搜尋樹的定義。
AVL-tree的加入
12
一、 LL型(左邊的左邊)
加入前的AVL-tree如下:
AVL-tree的加入
13
加入30後的AVL-tree如下:每個節點的上面數字
表示平衡因子。
AVL-tree的加入
14
此時50節點的|BF|>1,因此不為一棵AVL-tree,
其調整的方法乃將40往上提,50放在40的右
方,如下圖所示:
AVL-tree的加入
15
二、 RR型(右邊的右邊)
此RR型與LL型大同小異,如加入前的AVL-tree
為:
AVL-tree的加入
16
加入70後的AVL-tree為:
AVL-tree的加入
17
此時有一節點50,其|BF|>1,因此不為AVLtree,其型態為RR型,調整的方法乃將60往上
提,50放在60的左方,如下圖所示:
AVL-tree的加入
18
三、 LR型(左邊的右邊)
假設有一棵AVL-tree如下:
AVL-tree的加入
19
今加入45,則將變為不是一棵AVL-tree,它是屬
於LR型,因為加入的節點45位於節點
50(|BF|>1)的左邊的右邊。
AVL-tree的加入
20
調整的方式將45往上提,比45小的放在左邊,
比45大的放在右邊,結果如下所示:
AVL-tree的加入
21
四、RL型(右邊的左邊)
基本上RL型和LR型大致上類似。有一棵AVL-tree
如下:
AVL-tree的加入
22
今加入節點55後,將變成不是一棵AVL-tree,它
是RL型,因為加入的節點55,位於節點
50(|BF|>1)的右邊的左邊。
AVL-tree的加入
23
調整的方式將55往上提,並將小於55的節點放
在左邊,大於55的節點放在右邊,如下圖所
示:
失去平衡的AVL樹
24
(a ) 情 況 1 : 左 邊 的 左 邊
(b ) 情 況 2 : 右 邊 的 右 邊
失去平衡的AVL樹
25
(c ) 情 況 3 : 左 邊 的 右 邊
(d ) 情 況 4 : 右 邊 的 左 邊
進階 LL型
26
新 增 12 之 後
旋 轉 之 後
簡 單 右 旋 轉
新 增 4 之 後
複 雜 右 旋 轉
旋 轉 之 後
進階 RR型
27
簡 單 左 旋 轉
複 雜 左 旋 轉
進階 LR型
28
簡 單 的 向 右 旋 轉 兩 次
在 右 旋 轉 前 的 樹
旋 轉 前 的 樹
在 右 旋 轉 之 後
複 雜 的 向 右 旋 轉 兩 次
進階 RL型
29
簡 單 的 向 左 旋 轉 兩 次
旋 轉 前 的 樹
向 右 旋 轉 後
向 左 旋 轉 後
複 雜 的 向 左 旋 轉 兩 次
30
在下圖之平衡二元樹,加入 node 11 後,重新調
整之平衡樹為何?
31
AVL-tree的刪除
32
AVL-tree的刪除與二元搜尋樹的刪除相同,當刪
除的動作完成後,再計算平衡因子,作適當
的調整,直到平衡因子的絕對值皆小於等於
1。
1.
2.
3.
4.
找出關鍵路徑,計算路徑上每一節點的平衡
因子。
從樹根開始,找到最後一個平衡因子大於1以
上的節點,稱為關鍵節點。
決定調整種類(LL、RR、RL、LR)。
進行調整,必須保持二元搜尋樹的定義。
AVL-tree的刪除
33
EX1: 如果想要刪除節點50,因為它為一個樹葉
節點,所以可以直接將它刪除。
AVL-tree的刪除
34
AVL-tree的刪除
35
從樹根尋找關鍵節點(遇到第一個BF值的絕對值大
於1的節點)為30,當關鍵節點的BF值大於等於0時
往左子樹、小於0往右子樹找下一個節點,由於節
點30的BF值為2大於等於0,故往pivot節點的左子樹
找到節點20,其BF值大於等於0,找到此可知調整
型態為LL型,不需再往下搜尋。調整結果如下:
AVL-tree的刪除
36
AVL-tree的刪除
37
AVL Tree:
若欲刪除80,可找到
替代節點90(右子樹
中最小的節點),如
下圖所示:
AVL-tree的刪除
38
從樹根尋找關鍵節點,它是90那個節點,其BF
值為2大於0,往其左子樹尋找下一節點的BF值
為-1小於0,由此可知調整型態為LR型,結果如
下:

similar documents