algorithm - BST 时间分析

Question

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

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

Answer 1

是的。例如这棵树:

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

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