이진 탐색 vs 이진 탐색 트리

근본적으로 같은 원리에 의한 탐색 구조

 

이진 탐색

배열에 저장된 데이터를 탐색

- 동적으로 크기가 변하는 데이터 집합 탐색에는 부적합

- 삽입과 삭제가 상당히 힘들다

 

시간 복잡도

O(logN)

처음에 입력된 갯수가 N 이라 하면,
첫 시행 후에 반이 버려지게 되서 1/2 * N,

두번째 시행 후에 또 반이 버려져서 1/2 * 1/2 * N,

세번째 시행 후에 또 그 반이 버려져서 1/2 * 1/2 * 1/2 * N,

K번 시행후에는 (1/2)^K * N
이렇게 수행을 계속하다가 탐색이 끝나면 자료가 한개 남개 된다.
따라서 (1/2)^K * N ≒ 1
K = logN

이진 탐색 트리

연결 리스트 데이터에 대한 탐색

- 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조

- 삽입, 삭제가 빈번히 이루어진다면 반드시 이진 탐색 트리를 사용해야 함

 

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

- 균형 트리 : O(logn)
- 불균형 트리 : O(n) , 순차 탐색과 동일

 

수도 코드

 

 

 

재귀

TREE-SEARCH(x, k)
  if x = NULL or k = key[x]
    then return x
  if k < key[x]
    then return TREE-SEARCH(left[x], k)
    else return TREE-SEARCH(right[x], k)

 

 

반복

TREE-SEARCH(x, k)
  while x!=NULL and k!=key[x]
    do if k < key[x]
      then x <- left[x]
      else x <- right[x]
  return x