Chapter 9 高度平衡二元樹：AVL tree，斜張樹 - Ian-Liu-1990/Data-Structure GitHub Wiki

１. ＡＶＬ tree

1. 定義滿足條件，需求，甚至解釋什麼是AVL-Tree都TMD指同一件事

1. 可以是一棵空的二元搜尋樹Ｔ

2. 若Ｔ為非空的二元搜尋樹，且其每個節點的左，右子樹分別為ＴL和ＴR，若滿足

   1. ＴL與ＴR必須皆同時為高度平衡二元搜尋樹
   2. |ｈL-ｈR| <= 1，其中ｈL與ｈR分別為ＴL與ＴR的高度

3. 非空T的每個節點的左右子樹高度必須相差不得超過1，是高度平衡樹

• 考題 : 在AVL樹中各節點中之左子樹（TL）、右子樹（TR）之高度差為何？
• 考題 : 下列哪一棵不是AVL树
• 考題 : 下圖為何種資料結構

2. 平衡因子[AVL樹特性與檢查]

一棵二元搜尋樹的任意節點n，平衡因子BF(n) = ｈL-ｈR，BF(n)必須只能是-1，0，+1，其中ｈL與ｈR分別為節點n的左子樹ＴL與右子樹ＴR的高度

3. BST VS BST又符合AVL的特性

• 高度H的AVL Tree，節點數至少F(H+2) － １，其中F代表富比尼函式

富比尼	1	2	3	4	5
0	1	1	2	3	5

• 最大歪斜AVL Tree : 節點數最少而高度最高的AVL Tree
• AVL Tree的高度 : Log(N(全部節點數))
• 無法排序，強調樹高和搜尋時間

操作	BST的時間複雜度	BST-AVL的時間複雜度
搜尋	與樹高有關O(Ｈt)	尋找，平均和最壞情況下Ｏ(logn)
插入	與樹高有關O(Ｈt)	插入，平均和最壞情況下Ｏ(logn)
刪除	與樹高有關O(Ｈt)	刪除，平均和最壞情況下Ｏ(logn)
建一棵樹	O(N^2)~O(NlogN)	O(NlogN)

• 考題 : 假設只有一個節點的AVL樹的高度為0，請問高度為4的AVL樹最少有幾個節點

---

４. 插入與刪除造成的４個不平衡狀況

• 插入和刪除規則 ， 當平衡因子 >= 0 "往左走" ；平衡因子 < 0 "往右走"

1. 插入 : 是一棵二分搜尋樹，依照二分搜尋樹規則插入，每次從插入的點往樹根方向檢查最鄰近有問題的平衡因子，由平衡因子決定方向檢查LL，RR，LR，RL
2. 刪除 : 是一棵二分搜尋樹，依照二分搜尋樹規則刪除

   • 若刪除的節點是葉子，先從葉子向上找到問題節點，再從該節點向下，由平衡因子決定方向檢查LL，RR，LR，RL

   • 若刪除的節點是內部，依照二分搜尋樹或題目由該節點的右子樹最大鍵值取代，或該節點的左子樹最小鍵值取代，再從該節點向下，由平衡因子決定方向檢查LL，RR，LR，RL

５. 插入／刪除調整規則

1. LL : 從失去平衡的根開始L(路徑)-L(路徑)-L(路徑) 或 從失去平衡的根開始L(路徑)-L(路徑)-R(路徑)

   1. 將L(路徑)-L(路徑)之間的節點向上拉當作根

   2. 新Root的右子樹為原本的父節點，新Root的原本右子樹成為原本父節點的左子樹

   3. 新Root的左子樹為新Root的原本左子樹

2. RR : 從失去平衡的根開始R(路徑)-R(路徑)-R(路徑) 或 從失去平衡的根開始R(路徑)-R(路徑)-L(路徑)

   1. 將R(路徑)-R(路徑)之間的節點向上拉當作根

   2. 新Root的左子樹為原本的父節點，新Root的原本左子樹成為原本父節點的右子樹

   3. 新Root的右子樹為新Root的原本右子樹

3. LR : 從失去平衡的根開始N1-L(路徑)-N2-R(路徑)-N3

   1. 將L(路徑)-R(路徑)最後的節點N3向上拉當作根

   2. N1 > N3，N1變成N3的右子樹，若N3有右子樹則N3的右子樹變成N1的左子樹

   3. N2 < N3，N2變成N2的左子樹，若N3有左子樹則N3的左子樹變成N2的右子樹

4. RL : 從失去平衡的根開始N1-R(路徑)-N2-L(路徑)-N3

   1. 將R(路徑)-L(路徑)最後的節點N3向上拉當作根

   2. N1 < N3，N1變成N3的左子樹，若N3有左子樹則N3的左子樹變成N1的右子樹

   3. N2 > N3，N2變成N3的左子樹，若N3有右子樹則N3的右子樹變成N1的左子樹

---

AVL Tree 樹高Ｈ，最多含有多少節點? 最少含有多少節點?

考題集合

---

２. 斜張樹Ｓｐｌａｙ Tree

• 定義 : 不用平衡因子，Splay的動作將常運用(剛加入，搜尋，刪除)的節點帶往Root

1. 搜尋 :

2. 插入 :

3. 刪除 :