BST 성능 = 높이

아래 이진탐색트리(BST)를 보고, 조회성능에 대해 생각해보자.

결과적으로 말하자면, 밸런스가 맞춰져 있다면 O(logN) 의 성능을 보이고, 편향된 정도가 심할수록 O(N)의 성능을 보인다.

 

편향된 BST = 리스트 ??

이상하게 보일지 모르겠으나, 12를 루트노드로 갖는 BST라고 볼 수 있다

 

58을 찾기 위해선, 11번의 연산이 필요하다.

44를 찾기 위해선, 8번의 연산이 필요하다.

 

현재 조회과정은 O(N)의 성능을 보이며

결과적으로, [리스트] 자료구조 조회와 전혀 다를바가 없다!

 

BST가 편향될 수록, 조회성능이 점점 O(N)에 수렴하게 된다.

 

밸런스가 맞춰진 BST의 성능

똑같은 데이터로 조금 다른 BST를 만들어보면 어떻게 될까?

 

58을 찾기 위해선 4번의 연산이 필요하다

44를 찾기 위해서 4번의 연산이 필요하다

 

최대높이가 4이기 때문에, 어떤 데이터를 조회하려 해도 4번 이상의 연산횟수가 나올 수 없는 구조이다.

 

밸런스 맞춰진 BST의 빅-오 노테이션 성능은?

데이터가 N개 일 때, 밸런스가 맞춰진 이진트리의 최대 높이는 logN 이다.

이진트리에서의 조회&삽입&삭제 연산횟수는 이 높이와 비례한다.

따라서, 아래와 같이 기억하면 된다.

 

밸런스가 맞춰진 트리에서의 조회&삽입&삭제 연산은 모두 logN 이다