目錄
Part I — AVL Tree 1. AVL Tree 定義與性質 2. Balance Factor 與高度 3. AVL 的四種旋轉 4. AVL 插入 5. AVL 刪除 6. AVL 完整範例推演
Part II — Red-Black Tree 7. Red-Black Tree 定義與性質 8. RBT 的五條規則 9. RBT 插入 10. RBT 刪除 11. AVL vs Red-Black 比較
Part III — 由遍歷結果建構二元樹 12. Preorder + Inorder 建構 13. Inorder + Postorder 建構 14. 為什麼 Preorder + Postorder 不唯一？
Part I — AVL Tree
1. AVL Tree 定義與性質
AVL Tree（Adelson-Velsky & Landis, 1962）是一棵高度平衡的二元搜尋樹：
對每個節點，其左子樹與右子樹的高度差（Balance Factor）不超過 1。
高度保證
一棵含 N 個節點的 AVL tree，高度 h 滿足：
h < 1.44 × log₂(N + 2)
因此所有操作（search, insert, delete）最壞都是 O(log N)。
最少節點數（Fibonacci 關係）
高度 h 的 AVL tree 最少需要 N(h) 個節點：
N(0) = 1, N(1) = 2
N(h) = N(h-1) + N(h-2) + 1
h: 0 1 2 3 4 5 6
N(h): 1 2 4 7 12 20 33
2. Balance Factor 與高度
BF(node) = height(左子樹) − height(右子樹)
合法值: -1, 0, +1
BF = +2 → 左邊太重 → 需要旋轉
BF = -2 → 右邊太重 → 需要旋轉
高度定義： - 空樹 (nullptr): height = -1 - leaf 節點: height = 0 - 其他: height = 1 + max(height(left), height(right))
3. AVL 的四種旋轉
3.1 LL Case → 單右旋 (Right Rotation)
觸發： 不平衡節點 BF = +2，且其左子 BF ≥ 0。
z (+2) y
/ \ / \
y T4 → x z
/ \ / / \
x T3 T1 T3 T4
/ \
T1 T2
操作: y 上升為新 root，z 變成 y 的右子，y 的原右子 T3 變成 z 的左子
3.2 RR Case → 單左旋 (Left Rotation)
觸發： 不平衡節點 BF = -2，且其右子 BF ≤ 0。
z (-2) y
/ \ / \
T1 y → z x
/ \ / \ \
T2 x T1 T2 T3
/ \
T3 T4
操作: y 上升為新 root，z 變成 y 的左子，y 的原左子 T2 變成 z 的右子
3.3 LR Case → 先左旋再右旋 (Double Rotation)
觸發： 不平衡節點 BF = +2，且其左子 BF < 0。
z (+2) z (+2) x
/ \ / \ / \
y T4 → x T4 → y z
/ \ / \ / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
Step 1: 對 y 做左旋
Step 2: 對 z 做右旋
3.4 RL Case → 先右旋再左旋 (Double Rotation)
觸發： 不平衡節點 BF = -2，且其右子 BF > 0。
z (-2) z (-2) x
/ \ / \ / \
T1 y → T1 x → z y
/ \ / \ / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
Step 1: 對 y 做右旋
Step 2: 對 z 做左旋
判斷表
| 不平衡節點 BF | 子節點 BF | 旋轉 |
|---|---|---|
| +2 | ≥ 0 | LL → 右旋 |
| +2 | < 0 | LR → 左旋+右旋 |
| -2 | ≤ 0 | RR → 左旋 |
| -2 | > 0 | RL → 右旋+左旋 |
4. AVL 插入
- 像普通 BST 插入新節點（成為 leaf）。
- 從插入位置沿路徑回溯到 root。
- 更新每個節點的高度。
- 檢查 Balance Factor：若 |BF| > 1 → 旋轉。
- 插入最多需要一次旋轉（單旋或雙旋）。
5. AVL 刪除
- 像普通 BST 刪除（三種情況：leaf / 一個 child / 兩個 children）。
- 從刪除位置沿路徑回溯更新高度。
- 每遇到 |BF| > 1 → 旋轉。
- 與插入不同：刪除可能需要多次旋轉（O(log N) 次），因為旋轉可能使子樹高度減少，影響更上層。
6. AVL 完整範例推演
依序插入 10, 20, 30, 40, 50, 25：
Insert 10: Insert 20: Insert 30:
10 10 10 (BF=-2)
\ \
20 20
\
30
→ RR 左旋 at 10:
20
/ \
10 30
Insert 40: Insert 50:
20 20
/ \ / \
10 30 10 30 (BF=-2)
\ \
40 40
\
50
→ RR 左旋 at 30:
20
/ \
10 40
/ \
30 50
Insert 25:
20 (BF=-2)
/ \
10 40
/ \
30 50
/
25
→ RL 旋轉 at 20 (先對40右旋, 再對20左旋):
30
/ \
20 40
/ \ \
10 25 50
Part II — Red-Black Tree
7. Red-Black Tree 定義與性質
Red-Black Tree 是一種自平衡二元搜尋樹，每個節點多存一個顏色位元（紅 or 黑）。
透過顏色規則限制，保證樹的高度 ≤ 2 × log₂(N + 1)，因此所有操作 O(log N)。
C++ STL 的 std::set、std::map、std::multiset、std::multimap 底層都是 Red-Black Tree。
8. RBT 的五條規則
| # | 規則 | 說明 |
|---|---|---|
| 1 | 每個節點是紅色或黑色 | — |
| 2 | Root 是黑色 | — |
| 3 | 每個NIL（空節點）是黑色 | NIL 是葉節點的概念 |
| 4 | 紅色節點的兩個 children 都是黑色 | 不允許連續兩個紅色（No Red-Red） |
| 5 | 從任一節點到其所有後代 NIL 的路徑上，黑色節點數相同 | Black-Height 一致 |
Black-Height（黑高度）
從某節點到任何後代 NIL 經過的黑色節點數（不含自身）。
規則 5 保證：任何路徑的長度最多是最短路徑的 2 倍。
證明:
- 最短路徑：全黑 → 長度 = bh（black-height）
- 最長路徑：黑紅交替 → 長度 = 2 × bh
- 因此 h ≤ 2 × bh ≤ 2 × log₂(N + 1)
RBT 範例
8(B)
/ \
4(R) 12(R)
/ \ / \
2(B) 6(B) 10(B) 14(B)
/ \
1(R) 3(R)
Black-Height (from root) = 2
所有從 root 到 NIL 的路徑都恰好有 2 個黑色節點（不含 root 本身看法不同；含 root 則是 3）
9. RBT 插入
9.1 基本步驟
- 像普通 BST 插入，新節點塗紅色。
- 若違反規則 4（紅-紅衝突）→ 修復。
9.2 為什麼新節點是紅色？
如果塗黑，會破壞規則 5（增加某條路徑的 black-height）。紅色只可能違反規則 4，修復較簡單。
9.3 插入修復：三種情況
設新插入節點為 Z，其父親為 P，祖父為 G，叔叔為 U。
Case 1: Uncle U 是紅色 → 重新著色
G(B) G(R) ← 變紅（若 G 是 root 則保持黑）
/ \ / \
P(R) U(R) → P(B) U(B) ← 父和叔變黑
/ /
Z(R) Z(R)
然後以 G 為新的 Z，繼續往上檢查（可能一路到 root）。
Case 2: Uncle U 是黑色，Z 是 P 的「內側」child → 先旋轉成 Case 3
P 是 G 的左子，Z 是 P 的右子 (LR 形狀):
G(B) G(B)
/ \ / \
P(R) U(B) → Z(R) U(B) ← 對 P 左旋
\ /
Z(R) P(R)
然後變成 Case 3 的形狀。
Case 3: Uncle U 是黑色，Z 是 P 的「外側」child → 旋轉 + 重新著色
P 是 G 的左子，Z 是 P 的左子 (LL 形狀):
G(B) P(B) ← 變黑
/ \ / \
P(R) U(B) → Z(R) G(R) ← 變紅
/ \
Z(R) U(B)
操作: 對 G 右旋，交換 P 和 G 的顏色。
鏡像： 若 P 是 G 的右子，所有操作左右對稱。
9.4 插入修復總結
| Case | Uncle 顏色 | Z 的位置 | 操作 |
|---|---|---|---|
| 1 | 紅 | 任意 | P, U 變黑；G 變紅；Z = G 繼續 |
| 2 | 黑 | 內側 (LR / RL) | 旋轉 Z 到外側 → 變成 Case 3 |
| 3 | 黑 | 外側 (LL / RR) | 旋轉 G + P ↔ G 換色 → 完成 |
最多 O(log N) 次重新著色 + 至多 2 次旋轉。
10. RBT 刪除
RBT 的刪除是最複雜的操作。簡要流程：
- 像普通 BST 刪除（可能用中序後繼替代）。
- 若刪除的是紅色節點 → 無影響（black-height 不變）。
- 若刪除的是黑色節點 → black-height 可能失衡 → 需修復。
- 修復有 4 種情況（含鏡像共 8 種），通過旋轉和重新著色解決。
刪除修復 4 種情況
設 X 是替代被刪節點的位置，S 是 X 的 sibling，P 是 parent：
| Case | S 的顏色 | S 的 children | 操作 |
|---|---|---|---|
| 1 | 紅 | — | S↔P 換色，對 P 旋轉 → 轉成 Case 2/3/4 |
| 2 | 黑 | 兩個都黑 | S 變紅，X = P 往上繼續 |
| 3 | 黑 | 近側紅、遠側黑 | 近側child↔S 換色，對 S 旋轉 → 轉成 Case 4 |
| 4 | 黑 | 遠側紅 | S 取 P 的顏色，P 和遠側child 變黑，對 P 旋轉 → 完成 |
最多 O(log N) 次重新著色 + 至多 3 次旋轉。
11. AVL vs Red-Black 比較
| 項目 | AVL Tree | Red-Black Tree |
|---|---|---|
| 平衡條件 | BF | |
| 最大高度 | ~1.44 log₂ N | ~2 log₂ N |
| Search | 略快（更矮） | 略慢 |
| Insert | 至多 2 次旋轉 | 至多 2 次旋轉 |
| Delete | 至多 O(log N) 次旋轉 | 至多 3 次旋轉 |
| 額外空間/節點 | 高度 (int, 4 bytes) | 顏色 (1 bit) |
| 適用場景 | 查找密集 | 插入/刪除密集 |
| 實際應用 | 資料庫索引 | C++ STL, Java TreeMap, Linux 核心 |
選擇建議： - 查找遠多於插入/刪除 → AVL - 插入/刪除頻繁 → Red-Black - 不確定 → Red-Black（業界標準）
Part III — 由遍歷結果建構二元樹
12. Preorder + Inorder 建構
原理
- Preorder 的第一個元素 = root
- 在 Inorder 中找到 root → 左邊 = 左子樹，右邊 = 右子樹
- 由左子樹大小切分 Preorder → 遞迴建構
圖解
Preorder: [1, 2, 4, 5, 3, 6, 7]
Inorder: [4, 2, 5, 1, 6, 3, 7]
Step 1: root = 1 (Preorder 第一個)
Inorder 中 "1" 在 index 3 → 左子樹 [4,2,5] (3個), 右子樹 [6,3,7] (3個)
Step 2: 左子樹
Preorder: [2, 4, 5], Inorder: [4, 2, 5]
root = 2 → 左=[4], 右=[5]
Step 3: 右子樹
Preorder: [3, 6, 7], Inorder: [6, 3, 7]
root = 3 → 左=[6], 右=[7]
結果:
1
/ \
2 3
/ \ / \
4 5 6 7
演算法
buildFromPreIn(pre, preL, preR, in, inL, inR):
if preL > preR: return NULL
root = new Node(pre[preL])
rootIdx = find pre[preL] in in[inL..inR]
leftSize = rootIdx - inL
root.left = buildFromPreIn(pre, preL+1, preL+leftSize,
in, inL, rootIdx-1)
root.right = buildFromPreIn(pre, preL+leftSize+1, preR,
in, rootIdx+1, inR)
return root
時間複雜度
- 每次找 root 在 Inorder 中的位置：用 HashMap 預處理 → O(1)
- 總時間：O(N)
- 若不用 HashMap（線性搜尋）：O(N²) 最壞
13. Inorder + Postorder 建構
原理
- Postorder 的最後一個元素 = root（和 Preorder 正好相反）
- 在 Inorder 中找到 root → 切分左右
- 由右子樹大小切分 Postorder → 遞迴建構
- 注意：先建右子樹，再建左子樹（因為 Postorder 是 左→右→根，反過來就是 根→右→左）
圖解
Inorder: [4, 2, 5, 1, 6, 3, 7]
Postorder: [4, 5, 2, 6, 7, 3, 1]
Step 1: root = 1 (Postorder 最後一個)
Inorder 中 "1" 在 index 3 → 左子樹 [4,2,5], 右子樹 [6,3,7]
Step 2: 右子樹
Postorder: [6, 7, 3], Inorder: [6, 3, 7]
root = 3 → 左=[6], 右=[7]
Step 3: 左子樹
Postorder: [4, 5, 2], Inorder: [4, 2, 5]
root = 2 → 左=[4], 右=[5]
結果: 同上 — 同一棵樹！
演算法
buildFromInPost(in, inL, inR, post, postL, postR):
if postL > postR: return NULL
root = new Node(post[postR]) ← 最後一個是 root
rootIdx = find post[postR] in in[inL..inR]
rightSize = inR - rootIdx
root.right = buildFromInPost(in, rootIdx+1, inR,
post, postR-rightSize, postR-1)
root.left = buildFromInPost(in, inL, rootIdx-1,
post, postL, postR-rightSize-1)
return root
14. 為什麼 Preorder + Postorder 不唯一？
| 組合 | 能否唯一確定？ | 原因 |
|---|---|---|
| Preorder + Inorder | 能 | Inorder 可以切分左右子樹 |
| Inorder + Postorder | 能 | 同上 |
| Preorder + Postorder | 不能 | 無法區分左右子樹（除非是 Full Binary Tree） |
反例：
Preorder: [1, 2]
Postorder: [2, 1]
可能是: 也可能是:
1 1
/ \
2 2
兩棵不同的樹有相同的 Preorder 和 Postorder！
結論： 需要 Inorder 才能唯一切分左右子樹。
15. C++ 程式碼參照
| 檔案 | 內容 |
|---|---|
tree_avl.cpp |
AVL Tree 完整實作：insert, delete, 四種旋轉, 逐步視覺化 |
tree_red_black.cpp |
Red-Black Tree 完整實作：insert, delete, 修復, 顏色視覺化 |
tree_construct_from_traversals.cpp |
Preorder+Inorder 建構 + Inorder+Postorder 建構 + 驗證 |
編譯方式：
g++ -std=c++11 -Wall -o tree_avl tree_avl.cpp
g++ -std=c++11 -Wall -o tree_red_black tree_red_black.cpp
g++ -std=c++11 -Wall -o tree_construct_from_traversals tree_construct_from_traversals.cpp