이진탐색트리(Binary Search Tree)

이진 트리

• 이진 트리는 모든 노드가 정확하게 두 개의 서브트리를 가지고 있는 트리이다.

  • 다만 서브트리는 공백이 될 수 있다.

• 즉 노드의 유한 집합으로서 공백이거나 루트와 두 개의 분리된 이진트리인 경우 왼쪽서브트리와 오른쪽 서브트리로 구성된다.

  • 여기서 중요한점은 왼쪽과 오른쪽 서브트리를 확실하게 구분한다는 것이다.

    • 일반적인 트리에서 두개의 트리는 같지만 이진 트리에서는 두개의 트리는 다른 트리이다. 이는 이진트리에서는 서브트리의 위치가 다르기 때문이다.

    

• 편향 이진 트리(skewed binary tree)

  • 편향 이진트리란 모든 노드가 부모의 왼쪽 자식이기 때문에 왼편으로 편향되어 있거나 반대로 모든 노드가 부모의 오른쪽 자식으로 되어 오른쪽으로 편향되어 있어야 한다.

  

• 포화 이진트리(full binary tree)

  • 포화 이진트리란 이진트리가 보유할 수 있는 최대의 노드를 가지고 있는 형태이다.
  • 높이가 h인 이진 트리에서 있을 수 있는 최대 노드 수는2h⁺¹−1 이다.
  • 아래 그림은 높이가 2인 포화 이진트리이다.

  

• 완전 이진트리(complete binary tree)

  • 위 포화 이진트리 같은 경우에는 루트 노드를 1번으로 하고 레벨 별로 왼편에서 오른 편으로 차례로 노드 위치에 번호를 2h⁺¹−1까지 부여가 가능하다.
  • 그런데 만일 높이가 h이고 노드 수가 n, 일때 n <= ( $2^h⁺¹-1$ )인 이진트리를 노드의 레벨 순수에 따라 노드 번호를 붙인다면 이때 각 노드 번호의 위치가 포화 이진트리 번호 1에서 n까지의 위치와 모두 정확하게 일치한다면 이 트리를 완전 이진트리라고 한다.
  • 즉 루트 노드를 1이라고 하고 그외에 모든 노드가 왼쪽에서부터 오른쪽까지 꽉 차서 노드의 수가 n<=(2h⁺¹−1)라면 완전 이진트리이다. 아래 그림은 완전 이진트리의 예이다.

  

이진트리의 순차 표현

• 이진 트리는 유일하게 붙여지는 포화 이진 트리 번호를 이용하면 순차 표현 즉 1차원 배열로 쉽게 표현할 수 있다.
  • 즉 포화 이진트리 번호를 배열의 인덱스로 사용하면 된다.
  • 아래 그림은 이진 트리의 순차표현을 보여준다.
    • 이때 1차원 배열에시 인덱스 0은 실제 사용하지 않고 인덱스 1은 항상 루트 노드를 나타낸다.

• n개의 노드를 가진 이진트리를 1차원 배열로 표현했을 때 포화 이진트리 번호를 인덱스로 사용하면 어떤 노드 i의 부모, 왼쪽자식, 오른쪽 자식의 인덱스를 쉽게 알 수 있다.

<완전 이진트리를 표현한 1차원 배열에서 인덱스 관계>

• 장점
  • 이진트리의 순차표현은 어떠한 이진 트리의 표현에도 적용할 수 있다
• 단점
  • 저장공간을 효율적으로 사용하지 못할 수 있다는 단점
    • 그 예가 위에 편향 이진트리이다.
  • 트리의 중간에 삭제와 삽입을 하게 될 경우 많은 노드들의 이동이 불가피 하게 된다.

이진탐색 트리의 목적

• 이진탐색 + 연결리스트
  • 이진탐색 : 탐색에 소요되는 시간복잡도는 O(logN), but 삽입,삭제가 불가능
  • 연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), but 탐색하는 시간복잡도가 O(N)
  • 이 두가지를 합하여 장점을 모두 얻는 것이 '이진탐색트리'