BST에 대한 시간 분석

Question

BST의 시간 분석은 O (h)입니다. 여기서 h는 트리의 높이입니다.

BST 검색에서 O (n)을 완료 할 수 있습니까?

Answer 1

예입니다. 이 나무는 예를 들면 다음과 같습니다.

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

값이 8 이상인 경우 n (8) 회를 사용합니다.