BST的時間分析

Question

我知道，BST的時間分析是O（h），其中h是樹的高度。

是否有可能在BST上搜索O（n）完成？

Answer 1

是的。此樹例如：

1 
\ 
    2 
    \ 
    3 
    \ 
     4 
     \ 
     5 
     \ 
      6 
      \ 
      7 
      \ 
       8 

當查找值8或更大時，需要n（8）次比較。