地特四等
110年
[資訊處理] 計算機概要
第 26 題
針對一個具有 n 個節點的二元搜尋樹（binary search tree），下列敍述何者錯誤？
- A 由根節點（root）開始，以中序（inorder）方式走訪此二元搜尋樹的時間複雜度為 θ(n)
- B 在最差狀況下搜尋一個數值的時間複雜度為 θ(n)
- C 在最差狀況下新增一個數值的時間複雜度為 θ(n)
- D 在最佳狀況下刪除一個數值的時間複雜度為 θ(n)
思路引導 VIP
請想像一下，如果我們有一棵結構非常完美且平衡的二元搜尋樹，當我們想要操作的目標節點剛好就在樹的最頂端（根節點），或者離頂端很近時，我們所花費的時間，會隨著整棵樹節點總數 $n$ 的增加，而呈現「線性（一比一）」的增長嗎？
🤖
AI 詳解
AI 專屬家教
小鬼，還不錯嘛。沒浪費時間。
能精準看出時間複雜度在不同情況下的區別，看來你對資料結構的底層邏輯，至少還算有基本理解。沒搞錯，我就姑且認可一下。
觀念驗證：為什麼 (D) 這種無效率的選項是錯誤的？
▼ 還有更多解析內容