트리(Tree) - 비선형

• 방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없음

  ex. 조직도, 디렉토리 구조

• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가짐

• 정점이 n개인 트리는 반드시 n-1개의 간선을 가짐

• 루트에서 특정 정점으로 가는 경로는 유일

이진 트리

• 각 정점이 최대 2개의 자식을 가지는 트리
• 정점이 n개인 이진 트리는 최악의 경우 높이가 n
• 정점이 n개인 포화 또는 완전 이진 트리의 높이는 logN
• 높이가 h인 포화 이진트리는 2^h-1개의 정점을 가짐
• 이진트리가 응용되는 경우
  • 이진 탐색 트리
  • 힙
  • AVL트리
  • 레드 블랙 트리

완전 이진 트리

• 마지막 레벨을 제외하고 모든 정점이 채워져 있는 트리

포화 이진 트리

• 마지막 레벨도 모두 채워져 있는 트리

편향 트리

• 한 방향으로만 정점이 채워져 있는 트리