algorithm - BST的时间分析

Question

我知道，BST 的时间分析是 O(h)，其中 h 是树的高度。

是否有可能完成对 BST 的搜索需要 O(n)？

Answer 1

是的。例如这棵树：

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

查找 8 或更大的值时需要进行 n (8) 次比较。