[자료구조] #7_4 트리

** 이진 탐색 트리의 시간복잡도

• 트리의 높이(Depth)를 h라고 하면, 이진 탐색 트리의 시간복잡도는 O(h)
• n개의 노드를 가진다면, h = log(n) 에 가깝기 때문에, 시간복잡도는 O(log(n))
• 동작을 한번 실행 할 때마다 가능한 선택지가 반으로 줄여지기 때문에, 실행시간 역시 반으로 단축시킬 수 있다는 것을 의미한다.

 

클릭시 출처로 이동

 

 

 

** 이진 탐색 트리의 단점

• 트리가 균형 잡혀 있을 경우, 평균 시간복잡도 O(log(n))
• 최악의 경우, 링크드 리스트와 동일한 성능을 갖게 되고 시간복잡도는 O(n)