Q18.
對一個擁有n 個節點的二元樹(Binary Tree)進行搜尋某一個值x，在最壞情況下所需時間複雜度為多少？
電腦軟體設計共同科目 · 乙級 · Q18
難易度分析
3 / 5
此題要求考生區分一般二元樹與特定平衡結構的差異，並分析在最極端結構下（退化情形）的效能表現。由於需要識別出最壞情況的結構特徵，而非僅僅記憶常見的對數時間複雜度，因此設定為基礎理解層級。
正確答案：④θ(n)
④ θ(n):當二元樹退化成偏斜樹（所有節點僅有左子樹或僅有右子樹）時，結構等同於鏈結串列，搜尋必須逐一檢查所有 n 個節點，故最壞情況時間複雜度為 θ(n)。
錯誤選項解析
- ① θ(1):θ(1) 代表常數時間，僅在直接存取已知索引的陣列時才可能達成。在二元樹中搜尋特定值必須遍歷節點，不可能以常數時間完成。
- ② θ(log n):θ(log n) 是「平衡二元搜尋樹」的平均或最佳情況時間複雜度。本題針對一般二元樹的最壞情況，當樹退化成鏈結串列時無法達到對數時間。
- ③ θ(n log n):θ(n log n) 常見於高效排序演算法（如合併排序、堆排序）的時間複雜度，與二元樹搜尋無關。搜尋操作不會產生此複雜度。
Learning Tip
"本題核心考點在於區分「一般二元樹」與「二元搜尋樹」，以及「最壞情況」與「平均情況」的差異。常考陷阱是直覺選 θ(log n)，但只有在樹保持平衡的前提下才成立。實務上若需保證對數搜尋效率，應採用 AVL 樹 或 紅黑樹 等自平衡資料結構。"
學員答題分佈
①θ(1)0%
②θ(log n)0%
③θ(n log n)0%
④θ(n)0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！