地方政府公務人員四等-資訊處理類科計算機概要110 年第 26 題單選題
針對一個具有n個節點的二元搜尋樹（binary search tree），下列敍述何者錯誤？
A由根節點（root）開始，以中序（inorder）方式走訪此二元搜尋樹的時間複雜度為 $\theta(n)$
B在最差狀況下搜尋一個數值的時間複雜度為 $\theta(n)$
C在最差狀況下新增一個數值的時間複雜度為 $\theta(n)$
D在最佳狀況下刪除一個數值的時間複雜度為 $\theta(n)$正確答案
D正確答案
BST 最佳情況刪除為 θ(1)（如刪除葉節點），不是 θ(n)，故 D 錯誤。
為什麼答案是 D
最佳狀況下刪除（例如刪除的是根節點本身、或葉節點且從根直接找到）只需 θ(1)，不是 θ(n)，敘述錯誤，為本題答案。
載入中…
完整詳解
Pro · 無限重點 BST 最佳情況刪除為 θ(1)（如刪除葉節點），不是 θ(n)，故 D 錯誤。
反向題找錯誤。最佳狀況 = 最小可能成本，刪除葉節點只要 θ(1)。
逐選項分析
A✕
中序走訪必須拜訪每一個節點各一次，無論樹形如何，時間複雜度固定為 θ(n)，敘述正確。
B✕
BST 最差狀況為退化成鏈狀（skewed tree），搜尋需從根一路比對到葉，時間複雜度為 θ(n)，敘述正確。
C✕
新增數值需先找到插入位置，最差狀況同樣為退化樹，需走訪 n 個節點，時間複雜度 θ(n)，敘述正確。
D✓ 正確
最佳狀況下刪除（例如刪除的是根節點本身、或葉節點且從根直接找到）只需 θ(1)，不是 θ(n)，敘述錯誤，為本題答案。
BST 各操作時間複雜度
| 操作 | 最佳 | 平均 | 最差 |
|---|
| 搜尋 | θ(1) | θ(log n) | θ(n) |
| 新增 | θ(1) | θ(log n) | θ(n) |
| 刪除 | θ(1) | θ(log n) | θ(n) |
| 中序走訪 | θ(n) | θ(n) | θ(n) |
考生看到 θ(n) 直覺聯想 BST 最差情況就勾選為對，卻忽略題目問的是「最佳狀況」。最佳狀況下刪除應為 θ(1)，θ(n) 是最差狀況才對，此為最佳/最差對調的陷阱。 
