트리(Trees)

1 트리(Trees) 란?

• 정점(node)과 간선(edge)을 이용해 데이터의 배치 형태를 추상화한 자료 구조
• 뿌리(root) → 이파리(leaf)

2 트리의 특성

3 트리의 종류

3.1 이진 트리 (Binary Trees)

• 모든 노드의 차수가 2 이하인 트리
• 재귀적으로 정의할 수 있다
  • 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리
    (단, 모든 서브트리가 이진 트리)
  • terminal 조건: 빈 트리(empty tree)도 이진트리다

3.2 포화 이진트리 (Full Binary Tree)

• 모든 레벨에서 노드들이 모두 채워져 있는 이진트리 (높이가 k이고 노드의 개수가 $2^k - 1$인 이진트리)
  

3.3 완전 이진 트리 (Complete Binary Tree)

• 높이 k인 완전 이진 트리
• 레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
• 레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리