Tree

Tree (트리)

• 자료의 항목(node)들이 가지(dege)로 연결되어 구성된 구조
• 계층적인 구조 표현 시 사용
• 부모-자식 관계의 노드들로 구성

트리 관련 용어

• 노드 (node) : 트리를 구성하는 각 자료 항목
• 근 노드 (root node) 
  • 부모가 없는 최상위 노드
  • 트리 구조를 시작하는 노드
  • 제일 상위 계층에 존재하는 하나의 노드
• 자식 노드 : 임의의 노드에 연결된 다음 레벨의 노드들의 집합
• 부모 노드 : 임의의 노드에 연결된 상위 계층의 노드
• 단말 노드 : 자식 노드가 없는 노드
• 차수 (degree)
  
  • 각 노드의 자식 방향으로의 간선 개수
  • 한 노드에 연결된 가지의 수
  • 노드가 갖고 있는 자식 노드의 개수

• 레벨 : root node 레벨을 0으로 하고, 그 아래 가지로 연결된 노드들의 레벨 1씩 증가
• 트리의 깊이 (depth) : 어떤 특정 노드에서 root 노드에 이르는 경로의 길이
• 트리의 높이 (height) : 트리의 최대 레벨 + 1
• 트리의 크기가 N일때 전체 간선의 개수 = N-1

트리 구조의 저장

• 배열을 이용한 방법
• 연결 리스트를 이용한 방법

배열을 이용한 방법

• 연속적인 기억 공간을 그대로 이용하는 배열의 구조에 트리를 저장
• 각 노드 당 최대 차수 3만큼 기억 장소 확보
• 최대 기억 장소 : 총 노드의 개수  x 트리의 차수 + 1 = 28