algorithm - BST の時間分析

Question

BST の時間分析は O(h) で、h は木の高さです。

BST の検索が O(n) で完了することは可能ですか?

Answer 1

はい、そうです。たとえば、このツリー：

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

8 以上の値を探す場合、n (8) 回の比較が必要です。