下列那一個結構，採取空間換取時間的策略，藉以提昇在該結構中搜尋資料、新增、刪除的時間複雜度？
A二元搜尋樹（Binary Search Tree）
B紅黑樹（Red-Black Tree）
C有序鏈結串列（Sorted Linked List）
D雜湊表（Hash Table）正確答案
答案與詳解
D
正確答案
雜湊表用額外空間建立雜湊陣列，換取平均 O(1) 搜尋、新增、刪除時間。
為什麼答案是 D
雜湊表預先配置較大的陣列空間，透過雜湊函數直接定位，平均搜尋、新增、刪除皆為 O(1)，典型空間換時間。
載入中…
完整詳解
Pro · 無限重點 雜湊表用額外空間建立雜湊陣列，換取平均 O(1) 搜尋、新增、刪除時間。
秒殺技巧
看到「空間換時間」且搜尋為 O(1) → 幾乎 100% 是 Hash Table。逐選項分析
A✕
二元搜尋樹平均 O(log n)，最差會退化成 O(n)，且不屬於典型空間換時間設計。
B✕ 陷阱
紅黑樹是自平衡 BST，保證 O(log n)，屬於用「平衡規則」而非「空間」換取穩定時間。
C✕
有序鏈結串列搜尋、新增、刪除皆為 O(n)，既沒換空間也沒換到時間，最差選項。
D✓ 正確
雜湊表預先配置較大的陣列空間，透過雜湊函數直接定位，平均搜尋、新增、刪除皆為 O(1)，典型空間換時間。
各資料結構時間複雜度比較
| 結構 | 搜尋 | 新增 | 刪除 |
|---|---|---|---|
| 二元搜尋樹 | 平均 O(log n)／最差 O(n) | 同左 | 同左 |
| 紅黑樹 | O(log n) | O(log n) | O(log n) |
| 有序鏈結串列 | O(n) | O(n) | O(n) |
| 雜湊表 | 平均 O(1) | 平均 O(1) | 平均 O(1) |
陷阱提醒
考生容易把「紅黑樹保證 O(log n)」誤認為空間換時間。事實上紅黑樹是用平衡規則換穩定時間；真正以記憶體空間換取 O(1) 的是 Hash Table。