下列何者為在最差情況下（worst case），於一個一般性的二元搜尋樹（binary search tree）上做搜尋、插入、刪除動作的時間複雜度？
A搜尋為 O(log n)，刪除和插入為 O(n)
B三者皆為 O(log n)
C三者皆為 O(n)正確答案
D搜尋和插入為 O(log n)，刪除為 O(n)
答案與詳解
為什麼答案是 C
正解。一般BST若依序插入排序好的資料（如1,2,3,4,5），會退化成單邊鏈狀，樹高為n。此時搜尋、插入、刪除都要O(n)。
考點：搜尋複雜度錯誤考點：混淆平均與最差考點：退化成鏈狀考點：操作不對稱錯誤
載入中…
