Tree、Binary Tree、Balanced Binary Tree — 完整教學

---

目錄

1. Tree（樹）基本概念
2. Tree 的表示法
3. Tree 的遍歷（Traversal）
4. Binary Tree（二元樹）
5. Binary Tree 的性質與定理
6. Binary Tree 的遍歷
7. Binary Search Tree（二元搜尋樹, BST）
8. BST 的操作與複雜度
9. BST 退化問題
10. Balanced Binary Tree（平衡二元樹）
11. AVL Tree 詳解
12. AVL 的四種旋轉
13. AVL 插入與刪除
14. 各種樹的比較
15. C++ 程式碼參照

---

1. Tree（樹）基本概念

1.1 定義

樹 (Tree) 是一種非線性的資料結構，由節點（node）和邊（edge）組成。

一棵樹 T 是由 n ≥ 0 個節點組成的有限集合。若 n = 0 則為空樹；若 n ≥ 1，則： - 存在一個特殊節點稱為根 (root) - 其餘節點可分為 m ≥ 0 個互不相交的集合 T₁, T₂, …, Tₘ，其中每個集合本身也是一棵樹，稱為根的子樹 (subtree)。

1.2 基本術語

            A            ← root（根）
          / | \
         B  C  D         ← A 的 children（子節點）
        / \    |
       E   F   G         ← B 的 children; D 的 child
      /
     H                   ← E 的 child = leaf（葉節點）

術語	定義	上圖範例
Root（根）	沒有父節點的節點	A
Parent（父節點）	某節點的直接上層節點	B 是 E, F 的 parent
Child（子節點）	某節點的直接下層節點	E, F 是 B 的 children
Sibling（兄弟）	共享同一 parent 的節點	B, C, D 互為 sibling
Leaf（葉節點）	沒有 child 的節點（degree = 0）	C, F, G, H
Internal node	非 leaf 的節點	A, B, D, E
Degree（分支度）	一個節點的 child 數量	degree(A) = 3, degree(E) = 1
Depth（深度）	從 root 到該節點的邊數	depth(A) = 0, depth(E) = 2, depth(H) = 3
Height（高度）	從該節點到最深 leaf 的邊數	height(A) = 3, height(B) = 2, height(C) = 0
Level	同一深度的所有節點	Level 0: {A}, Level 1: {B,C,D}
Path（路徑）	從一節點到另一節點經過的邊	A→B→E→H 是一條路徑
Subtree（子樹）	某節點及其所有後代	以 B 為根的子樹:
Forest（森林）	多棵互不相交的樹	移除 root A → 三棵樹

1.3 樹的性質

• 有 N 個節點的樹恰好有 N − 1 條邊。
• root 到任何節點的路徑唯一。
• 樹中沒有環 (cycle)。
• 連通且無環的圖 = 樹。

---

2. Tree 的表示法

2.1 鏈結表示法（最常用）

每個節點存： - 資料 (data) - 指向所有 children 的指標

常見做法：「左子右兄弟法 (Left-Child Right-Sibling)」

struct TreeNode {
    int data;
    TreeNode* firstChild;    // 指向第一個 child
    TreeNode* nextSibling;   // 指向右邊的 sibling
};

原始樹:          左子右兄弟表示:
     A                A
   / | \             /
  B  C  D           B → C → D
 / \    |          /         /
E   F   G        E → F     G
/                /
H               H

2.2 陣列表示法（完全二元樹適用）

• 節點 i 的 left child = 2i + 1
• 節點 i 的 right child = 2i + 2
• 節點 i 的 parent = (i − 1) / 2

---

3. Tree 的遍歷（Traversal）

一般樹的遍歷有兩大類：

3.1 深度優先搜尋 (DFS)

• Preorder（前序）：先訪問 root，再依序遞迴訪問各子樹。
• Postorder（後序）：先遞迴訪問各子樹，最後訪問 root。

Preorder:  A B E H F C D G
Postorder: H E F B C G D A

3.2 廣度優先搜尋 (BFS) / Level-Order

使用 Queue，逐層遍歷：

Level-order: A B C D E F G H

---

4. Binary Tree（二元樹）

4.1 定義

二元樹 (Binary Tree) 是一種特殊的樹，每個節點最多只有兩個 child，分別稱為左子 (left child) 和右子 (right child)。

注意：二元樹區分左右。只有左子 ≠ 只有右子。

      1
     / \
    2   3
   / \   \
  4   5   6
     /
    7

4.2 特殊二元樹

名稱	定義	示意
Full Binary Tree（滿二元樹）	每個節點有 0 或 2 個 children（沒有只有一個 child 的）	每層都是滿的（最後一層除外）
Complete Binary Tree（完全二元樹）	除最後一層外每層都是滿的，最後一層節點靠左排列	Heap 的基礎結構
Perfect Binary Tree（完美二元樹）	所有 internal node 都有 2 個 children，且所有 leaf 在同一層	高度 h → 節點數 2^(h+1) − 1
Skewed Binary Tree（歪斜樹）	每個節點最多一個 child → 退化成 linked list	左歪斜 or 右歪斜

Perfect:          Complete:         Full:           Skewed:
     1                1               1               1
    / \             / \             / \             /
   2   3           2   3           2   3           2
  / \ / \         / \             / \             /
 4  5 6  7       4   5           4   5           3
                                                /
                                               4

---

5. Binary Tree 的性質與定理

性質	說明
第 i 層最多有 2^i 個節點	Level 0 (root): 1, Level 1: 2, Level 2: 4, ...
高度 h 的二元樹最多 2^(h+1) − 1 個節點	Perfect binary tree
高度 h 的二元樹最少 h + 1 個節點	Skewed tree
n 個節點的二元樹高度：⌊log₂ n⌋ ≤ h ≤ n − 1	最佳 = 平衡, 最差 = 歪斜
若 leaf 數 = n₀, degree-2 node 數 = n₂, 則 n₀ = n₂ + 1	任何二元樹都成立

---

6. Binary Tree 的遍歷

6.1 四種遍歷方式

         1
        / \
       2   3
      / \   \
     4   5   6

遍歷	順序	結果	口訣
Preorder（前序）	Root → Left → Right	1 2 4 5 3 6	「根左右」
Inorder（中序）	Left → Root → Right	4 2 5 1 3 6	「左根右」
Postorder（後序）	Left → Right → Root	4 5 2 6 3 1	「左右根」
Level-order（層序）	逐層由左到右	1 2 3 4 5 6	使用 Queue

6.2 Inorder 的特殊性質

對二元搜尋樹 (BST)，inorder 遍歷會得到排序後的序列。

6.3 由遍歷結果重建二元樹

• Preorder + Inorder → 唯一確定一棵二元樹
• Postorder + Inorder → 唯一確定一棵二元樹
• Preorder + Postorder → 不能唯一確定（除非是 full binary tree）

原理： - Preorder 的第一個元素 = root - 在 Inorder 中找到 root 的位置 → 左邊 = 左子樹，右邊 = 右子樹 - 遞迴處理

例：

Preorder: 1 2 4 5 3 6
Inorder:  4 2 5 1 3 6

Step 1: root = 1 (Preorder 第一個)
Step 2: Inorder 中 "1" 的位置 → 左: [4,2,5], 右: [3,6]
Step 3: 左子樹 Preorder: [2,4,5], Inorder: [4,2,5] → root=2, 左=[4], 右=[5]
Step 4: 右子樹 Preorder: [3,6], Inorder: [3,6] → root=3, 左=[], 右=[6]

---

7. Binary Search Tree（BST）

7.1 定義

BST 是一種二元樹，每個節點滿足：

左子樹所有節點的值 < 當前節點的值 < 右子樹所有節點的值

         8
        / \
       3   10
      / \    \
     1   6   14
        / \  /
       4   7 13

7.2 BST 的基本操作

操作	平均	最壞（退化）	說明
Search	O(log N)	O(N)	類似 binary search
Insert	O(log N)	O(N)	找到正確位置，建新節點
Delete	O(log N)	O(N)	三種情況（見下文）
FindMin	O(log N)	O(N)	一路往左走
FindMax	O(log N)	O(N)	一路往右走
Inorder	O(N)	O(N)	輸出排序序列

7.3 BST 刪除的三種情況

設要刪除節點 X：

Case 1: X 是 leaf → 直接移除。

刪除 4:
     5          5
    / \   →    / \
   3   7      3   7
  / \          \
 2   4          (移除)

Case 2: X 有一個 child → 用 child 取代 X。

刪除 3 (只有左子):
     5          5
    / \   →    / \
   3   7      2   7
  /
 2

Case 3: X 有兩個 children → 找 X 的中序後繼 (inorder successor)（右子樹的最小值）或中序前驅 (inorder predecessor)（左子樹的最大值），用其值取代 X，再遞迴刪除那個替代節點。

刪除 8:
         8               9
        / \             / \
       3   10    →     3   10
      / \    \        / \    \
     1   6   14      1   6   14
        / \  /          / \  /
       4   7 13        4   7 13

步驟: 8 的中序後繼 = 右子樹最小 = 9 (假設有)
      用 9 取代 8，然後刪除原來的 9

---

8. BST 的操作與複雜度

8.1 Search（搜尋）

search(node, key):
    if node is NULL: return NOT_FOUND
    if key < node.data: return search(node.left, key)
    if key > node.data: return search(node.right, key)
    return node  // found

每次比較淘汰一半 → 平均 O(log N)（若平衡）。

8.2 Insert（插入）

insert(node, key):
    if node is NULL: return new Node(key)
    if key < node.data: node.left  = insert(node.left, key)
    if key > node.data: node.right = insert(node.right, key)
    return node

新節點一定插入為 leaf。

8.3 Inorder Traversal（中序遍歷）

inorder(node):
    if node is NULL: return
    inorder(node.left)
    visit(node)
    inorder(node.right)

對 BST 得到遞增排序的結果。

---

9. BST 退化問題

若插入順序為已排序的序列（如 1, 2, 3, 4, 5），BST 會退化為 linked list：

插入 1, 2, 3, 4, 5:

1
 \
  2
   \
    3
     \
      4
       \
        5

高度 = N - 1 → 所有操作變 O(N)！

解決方案：使用平衡二元樹 (Balanced BST)。

---

10. Balanced Binary Tree（平衡二元樹）

10.1 定義

一棵二元樹是高度平衡的 (height-balanced)，如果對每個節點，其左右子樹的高度差不超過 1。

平衡:                    不平衡:
      4                       1
     / \                       \
    2   6                       2
   / \ / \                      \
  1  3 5  7                      3
                                  \
                                   4
height diff = 0 everywhere      height diff = 3 at root

10.2 為什麼需要平衡？

結構	高度	Search/Insert/Delete
平衡 BST	O(log N)	O(log N) — 保證
退化 BST	O(N)	O(N) — 最壞

10.3 常見的平衡 BST

名稱	平衡條件	旋轉複雜度	特點
AVL Tree	每個節點左右高度差 ≤ 1	插入/刪除 O(log N)	嚴格平衡, 查找最快
Red-Black Tree	著色規則限制最長路徑 ≤ 2×最短	插入/刪除 O(log N)	略鬆平衡, 插入/刪除常數較小, C++ STL set/map 底層
Splay Tree	每次存取的節點旋轉到 root	攤銷 O(log N)	無需額外儲存平衡資訊
B-Tree / B+ Tree	多路平衡搜尋樹	O(log N)	磁碟/資料庫用

---

11. AVL Tree 詳解

11.1 定義（Adelson-Velsky & Landis, 1962）

AVL Tree 是一棵 BST，對每個節點滿足：

|height(left subtree) − height(right subtree)| ≤ 1

此差值稱為 Balance Factor (BF)：

BF(node) = height(left) − height(right)

合法的 BF 值：-1, 0, +1。

11.2 AVL 的高度保證

一棵有 N 個節點的 AVL tree，高度 h 滿足：

h ≤ 1.44 × log₂(N + 2) − 0.328

也就是 h = O(log N)，這保證了所有操作最壞 O(log N)。

11.3 最少節點數（與 Fibonacci 的關係）

高度 h 的 AVL tree 最少需要 N(h) 個節點：

N(0) = 1
N(1) = 2
N(h) = N(h-1) + N(h-2) + 1    ← 類似 Fibonacci！

h:    0  1  2  3  4   5   6
N(h): 1  2  4  7  12  20  33

---

12. AVL 的四種旋轉

當插入或刪除後某節點的 BF 變為 +2 或 -2，需要旋轉來恢復平衡。

12.1 LL（Left-Left）— 右旋（Single Right Rotation）

情境： 新節點插入在不平衡節點的左子的左子樹。

失衡前:          右旋後:
      z (+2)         y
     / \            / \
    y   T4         x   z
   / \            /   / \
  x   T3         T1  T3  T4
 / \
T1  T2

操作： 以 z 為軸右旋 → y 上升成新 root，z 變成 y 的右子。

12.2 RR（Right-Right）— 左旋（Single Left Rotation）

情境： 新節點插入在不平衡節點的右子的右子樹。

失衡前:          左旋後:
  z (-2)             y
 / \                / \
T1  y              z   x
   / \            / \   \
  T2  x          T1  T2  T3
     / \
    T3  T4

操作： 以 z 為軸左旋 → y 上升。

12.3 LR（Left-Right）— 先左旋再右旋（Double Rotation）

情境： 新節點插入在不平衡節點的左子的右子樹。

失衡前:           先對 y 左旋:        再對 z 右旋:
      z (+2)          z (+2)              x
     / \             / \                 / \
    y   T4          x   T4             y     z
   / \             / \                / \   / \
  T1  x           y   T3            T1 T2 T3  T4
     / \         / \
    T2  T3      T1  T2

操作： 先對 y 做左旋，再對 z 做右旋。

12.4 RL（Right-Left）— 先右旋再左旋（Double Rotation）

情境： 新節點插入在不平衡節點的右子的左子樹。

失衡前:           先對 y 右旋:        再對 z 左旋:
  z (-2)            z (-2)               x
 / \               / \                  / \
T1  y             T1  x               z     y
   / \               / \             / \   / \
  x   T4            T2  y          T1  T2 T3  T4
 / \                   / \
T2  T3                T3  T4

12.5 如何判斷用哪種旋轉？

不平衡節點 BF	其 child BF	旋轉類型
+2 (左重)	+1 或 0 (左子左重)	LL → 右旋
+2 (左重)	-1 (左子右重)	LR → 左旋+右旋
-2 (右重)	-1 或 0 (右子右重)	RR → 左旋
-2 (右重)	+1 (右子左重)	RL → 右旋+左旋

---

13. AVL 插入與刪除

13.1 插入流程

1. 像普通 BST 一樣插入新節點（一定插入為 leaf）。
2. 從插入位置沿著路徑往上回溯到 root。
3. 更新每個節點的高度。
4. 計算每個節點的 Balance Factor。
5. 遇到第一個 |BF| = 2 的節點 → 根據情況做旋轉。
6. 旋轉後，其上方的節點也已平衡（插入只需至多一次旋轉）。

13.2 插入範例

依序插入: 10, 20, 30, 40, 50, 25

Step 1: Insert 10        Step 2: Insert 20       Step 3: Insert 30
   10                       10                       10 (-2) ← 不平衡!
                              \                        \
                              20                       20
                                                        \
                                                        30
→ RR 旋轉:
   20
  /  \
 10   30

Step 4: Insert 40        Step 5: Insert 50
     20                       20
    /  \                     /  \
   10   30                  10   30 (-2) ← 不平衡!
          \                        \
          40                       40
                                     \
                                     50
→ 在 30 做 RR 旋轉:
     20
    /  \
   10   40
       /  \
      30   50

Step 6: Insert 25
       20 (-2) ← 不平衡!
      /  \
     10   40
         /  \
        30   50
       /
      25
→ 在 20 做 RL 旋轉 (先對 40 右旋, 再對 20 左旋):
       30
      /  \
     20   40
    /  \    \
   10  25   50

13.3 刪除流程

1. 像普通 BST 一樣刪除節點。
2. 從刪除位置沿路徑往上回溯更新高度。
3. 每遇到 |BF| = 2 → 旋轉。
4. 與插入不同：刪除可能需要多次旋轉（因為旋轉後高度可能縮減，影響更高層）。

---

14. 各種樹的比較

特性	普通 Tree	Binary Tree	BST	AVL Tree	Red-Black Tree
子節點數	不限	≤ 2	≤ 2	≤ 2	≤ 2
排序性	無	無	有	有	有
平衡保證	無	無	無	嚴格 (	BF
Search 最壞	—	O(N)	O(N)	O(log N)	O(log N)
Insert 最壞	—	—	O(N)	O(log N)	O(log N)
Delete 最壞	—	—	O(N)	O(log N)	O(log N)
旋轉次數(插入)	—	—	—	≤ 2	≤ 2
旋轉次數(刪除)	—	—	—	O(log N)	≤ 3
額外空間/節點	—	—	—	高度 (int)	顏色 (1 bit)
典型應用	檔案系統	表達式樹	簡單搜尋	頻繁查找	STL set/map

---

15. C++ 程式碼參照

檔案	內容	重點
tree_general.cpp	一般樹（左子右兄弟）、DFS/BFS 遍歷	一般樹的結構與遍歷
tree_bst.cpp	BST 完整操作：insert, search, delete, traversals, findMin/Max	BST 的三種刪除情況
tree_avl.cpp	AVL Tree：insert, delete, 四種旋轉, 高度更新, BF 計算	旋轉的實作與視覺化

編譯方式：

g++ -std=c++11 -Wall -o tree_general tree_general.cpp
g++ -std=c++11 -Wall -o tree_bst tree_bst.cpp
g++ -std=c++11 -Wall -o tree_avl tree_avl.cpp