阿摩線上測驗
11. 在有N個節點的二元樹中作搜尋的運算，其執行時間跟何者成正比?
(A) N
(B) log N
(C) N2
(D) N log N
統計： A(38), B(168), C(18), D(21), E(0) #2847104
詳解 (共 1 筆)
【解題思路】
這題考的是 Binary Search Tree（二元搜尋樹） 的搜尋時間。
最重要的觀念：
平衡的二元搜尋樹（Balanced BST）
→ 搜尋時間 O(log N)
原因：
每次比較後都會把搜尋範圍「砍一半」，
就像二分搜尋（binary search）一樣。
例如：
-
N=16 → log₂1 6 = 4
-
N=1024 → log₂1 024 = 10
-
N=1,000,000 → log₂1M ≈ 20
你看到沒？
節點越多，只會增加「少量」搜尋步驟。
因此正常情況下，二元樹搜尋的時間與：
log N 成正比。
所以答案是 (B) log N。
【為什麼其他選項不正確（逐一破題）】
(A) N
→ 這是「最壞情況」的時間（樹退化成鏈表），
但題目問的是一般搜尋時間 → 不選。
(B) log N
→ 正確！
平衡二元搜尋樹的搜尋效率。
(C) N²
→ 完全不可能出現，二元樹沒有平方級時間。
(D) N log N
→ 這是排序或合併類演算法常見時間，
與單次搜尋無關。
【延伸知識】
二元搜尋樹（BST）搜尋複雜度：
-
最佳情況：O(1)（剛好是根）
-
平均情況：O(log N)（樹大致平衡）
-
最壞情況：O(N)（完全歪成一條鏈，如只往右插）
平衡樹（AVL、Red-Black Tree）
強制維持平衡 → 搜尋時間一定是 O(log N)。
【記憶技巧】
一句話：
二元搜尋樹 = Binary Search
Binary Search = log N
【常見錯誤】
-
看到 N 就選 → 那是「最壞情況」
-
不知道樹高 = log N
-
把一般樹和二元搜尋樹搞混
-
把 N log N（排序常用）誤以為是搜尋
【一、二元樹是什麼？（最基本理解）】
二元樹（Binary Tree）是一種階層式的資料結構，每個節點 最多有 2 個子節點：
-
左子樹（Left Subtree）
-
右子樹（Right Subtree）
只要記住：
一個節點最多兩個子節點 → 就叫二元樹。
結構長得像：
【二、二元樹常見分類（考試重點）】
1. 一般二元樹（Binary Tree）
-
每個節點最多 2 個子節點
-
不保證左右的順序或大小
2. 滿二元樹（Full Binary Tree）
-
除了葉節點外，每個節點都有 2 個子節點
3. 完全二元樹（Complete Binary Tree）
-
每一層都滿，最後一層從左到右填滿
（常用於堆積 heap）
4. 二元搜尋樹（Binary Search Tree, BST）
（農會電腦概論高機率考這個）
-
左子樹 < 根 < 右子樹
-
特別適合搜尋（平均時間 O(log N)）
【三、二元樹的高度、高度的考法（重點）】
樹的高度定義：
-
樹根為高度 1（有些教材為 0，但考試通常採「1-based」）
若樹高 h，則：
-
最多節點數：2^h − 1
-
最少節點數：h（如果退化成一條鏈）
農會常考題型：
「有 N 個節點，樹的高度可能是？」
你答對過那題「4 個節點，高度可能為 2、3」。
原因：
-
最矮：log₂(N+1)
-
最高：N（像一條直線）
【四、二元樹搜尋的考點（非常常考）】
二元搜尋樹（BST）的搜尋時間：
-
平均：O(log N)
-
最差：O(N)
考題會問：
在有 N 個節點的二元樹中作搜尋，其執行時間跟何者成正比？
答案：log N（考平均、或平衡情況）
但如果題目說「未經平衡、最壞情況」→ 才會變成 O(N)。
【五、二元樹的走訪（Traversal）三大必考】
記住 DFS 三種順序：
-
前序（Preorder）
根 → 左 → 右
記法：「根最急，先出手」 -
中序（Inorder）（BST 排序會用到）
左 → 根 → 右
記法：「左邊排隊，根卡中間」 -
後序（Postorder）
左 → 右 → 根
記法：「小孩先，爸爸後」
這三個很常出現在輸入輸出題。
