BST的時間複雜度

Question

所以我知道由於結構減半，BST上的操作在日誌時間內運行，所以我在想如果搜索一個不在結構中的值，時間複雜度會是多少。

Answer 1

平均案例時間複雜度將是O（log n），最壞的情況是O（n）。如果您想了解可以參考What does O(log n) mean exactly?

的O（log n）的複雜程度，該圖像將解釋如何部分：

我還將建議要經過wiki瞭解詳情。

Answer 2

它仍然是O（log n）。這樣想，它會一直搜索直到找不到。