새소식

자료구조&알고리즘/자료구조

이진 트리 / 이진 탐색 트리

  • -

트리

하나의 뿌리(루트)에서 자식 노드를 가지고 간선(Edge)으로 연결된 구조이다.

 

그래프와 트리의 차이점은 무엇인가?

  • 트리는 순환 구조를 갖지 않는 그래프이다.
  • 그래프는 단방향, 양방향을 모두 가리킬 수 있지만, 트리는 부모 노드에서 자식 노드를 가리키는 단방향만 존재한다.

 

이진 트리

최대 2개의 자식을 갖는 형태의 트리이다.

 

 

이진 트리 vs 이진 탐색 트리

  • 이진 트리: 최대 2개의 자식을 갖는 트리
  • 이진 탐색 트리: 이진 트리에 추가적인 조건이 존재하는 트리
    • 노드의 왼쪽 하위 트리에는 노드의 값보다 작은 값의 노드만 존재한다.
    • 노드의 오른쪽 하위 트리에는 노드의 값보다 큰 노드만 존재한다.

 

 

이진 탐색 트리를 사용하는 이유

  • 이진 탐색 트리의 시간 복잡도 → 트리의 높이가 h라고 한다면 → O(h)
  • 데이터의 수로 표기하는게 정석이므로 그렇게 표기를 한다면
    모든 노드가 빈 자리 없이 꽉꽉 채워져있는 포화 이진 트리일 경우
    → 포화 이진 탐색 트리를 구성하고 있는 노드의 개수가 n개일 때, $ n = 2^h - 1 $ 이므로
    h = log(n-1)

    O(h) = O(log(n-1)) = > O(logn)
  • 배열 탐색의 시간복잡도 → O(n)
     

 

  • 반면, 트리가 아래 그림처럼 한쪽으로 치우친 경우에는 $ h = n $ 이므로 O(n)의 시간복잡도를 갖는다.

 

 

 

728x90
Contents