下列何者為在最差情況下（worst case），於一個一般性的二元搜尋樹（binary search tree）上做搜尋、插入、刪除動作的時間複雜度？
A搜尋為 O(log n)，刪除和插入為 O(n)
B三者皆為 O(log n)
C三者皆為 O(n)正確答案
D搜尋和插入為 O(log n)，刪除為 O(n)
答案與詳解
逐選項解析
A搜尋為 O(log n)，刪除和插入為 O(n)搜尋複雜度錯誤✕ 錯誤
搜尋在最差情況不是O(log n)。當BST退化成斜樹（鏈狀）時，搜尋也要走過所有節點，同樣是O(n)。
B三者皆為 O(log n)混淆平均與最差✕ 易錯陷阱
這是「平均情況」或「平衡BST」（如AVL、紅黑樹）的複雜度。一般BST不保證平衡，最差情況不是O(log n)。最常見陷阱選項。
C三者皆為 O(n)✓ 正確
D搜尋和插入為 O(log n)，刪除為 O(n)✕ 錯誤
立即註冊,看完整詳解
這題的完整詳解,註冊就能看 · 每天 2 題免費
- 完整逐選項解析
- 秒殺解題技巧與破題關鍵
- 關鍵知識表整理
- 陷阱與易錯提醒
- 同考點歷屆題庫連續刷題與錯題本
立即註冊觀看完整詳解 已有帳號?登入
