참고자료

• https://rosweet-ai.tistory.com/55
• https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC
• https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254
• https://doyoung.tistory.com/9
• https://www.penjee.com

1. 이진 트리란?

이진 트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 노드 자식 노드라고 한다.

그림에서 보는 이진 트리는 다음과 같은 규칙을 가지고 있다.

• 이진트리는 항상 두개의 자식 노드를 가지고 있다.
• 모든 원소는 중복된 값을 가져서는 안된다.
• 왼쪽 서브트리에 존재하는 노드들의 값은 그 트리의 루트 값보다 반드시 작다.
• 오른쪽 서브트리에 존재하는 노드들의 값은 그 트리의 루트 값보다 반드시 크다.

이진트리는 주로 검색 알고리즘, 정렬 알고리즘 등에 사용되는데 자료의 삽입, 삭제, 검색 등의 작업이 빠르게 수행될 수 있으며, 일반적으로 O(log n) 시간 복잡도를 가지는 알고리즘을 사용하여 이러한 작업이 수행된다.

2. 이진 트리의 종류

1) 정 이진 트리(Full binary tree)

• 모든 노드가 2개의 자식을 가지거나 자식이 없는 경우에는 정 이진 트리(Full Binary Tree)라고 한다.
  자식이 한 개인 경우가 없어야 정 이진 트리이다.

  (1) 정 이진 트리의 유효 및 무효 구조

  

2) 완전 이진 트리(Complete binary tree)

• 완전 이진 트리는 두가지 조건을 충족해야 한다.
  • 마지막 레벨(level)을 제외하고 모든 노드가 채워져 있어야 한다.
  • 노드는 왼쪽에서 오른쪽 방향으로 채워져야 한다.

    (1) 완전 이진 트리의 유효 및 무효 구조

    

3) 포화 이진 트리(Perfect binary tree)

• 모든 노드가 2개의 자식을 가지고 잎 노드가 모두 같은 레벨(level)일때는 포화 이진 트리(Perfect binary tree)라고 한다.
• 모든 레벨(level)의 노드가 꽉 차있기 때문에 자식노드의 개수가 2의 제곱수만큼 증가하여 노드의 총 개수는 (2^(k+1))-1의 특징을 갖는다.
• 높이가 h일 때 leaf노드의 개수는 2의 h제곱 개수가 된다.

  (1) 포화 이진 트리의 유효 및 무효 구조

  

4) 균형 이진 트리(Balanced binary tree)

• 각 노드의 왼쪽과 오른쪽 서브 트리의 높이가 최대 1만큼 차이가 나는 이진 트리
• AVL 트리와 레드-블랙 트리는 균형 이진 탐색 트리를 생성/유지하는 잘 알려진 데이터 구조

  (1) 균형 이진 트리의 유효 및 무효 구조

  

5) 변질 이진 트리(Degenerate binary tree)

• 모든 부모 노드가 자식 노드를 하나만 가지는 이진 트리
• 퇴화된 이진 트리의 높이는 해당 트리에 있는 노드의 총 개수와 같다.

  (1) 변질 이진 트리의 유효 및 무효 구조

  

6) 번외

노드 한개면 위의 모든 조건에 부합하게 되는데 이는 싱글노드트리라고 한다.