2.5 트리

2.5.1 트리의 개념

트리 - 데이터 간의 관계를 나타내는 중요한 비선형 자료구조.
예) 족보(가계도), 기업이나 학교의 조직도

트리는 데이터가 저장되는 노드(node)와 노드를 연결하는 가지(branch, edge)로 구성.
• 노드- 계층적인 관계

• 트리 - 정보 항목과 가지를 합친 것.
• 루트(root) - 빈 트리(노드의 개수가 0인 트리)가 아닌 경우에 맨 꼭대기에 있는 하나의 노드.
• 차수(degree) - 각 노드에 있는 아래로 향하는 가지의 수.
• 트리의 차수 - 트리의 모든 노드의 차수 중에서 제일 큰 차수.
• 단말 노드(terminal node) / 잎 노드(leaf node)- 노드의 차수가 0인 노드(자식 노드를 가지지 않는 노드).
• 비단말 노드/내부(internal) 노드 - 루트 노드와 단말 노드를 제외한 나머지 노드.
• 부모 노드(parent node) - 아래로 연결된 노드의 바로 위에 있는 노드
• 자식 노드(child node) - 위로 연결된 노드의 바로 아래에 있는 노드
• 형제(sibling) 노드 - 같은 부모를 가진 노드.

• 어떤 노드 X의 조상(선조, ancestor) 노드 - 루트 노드로부터 어떤 노드 X까지의 경로(가지들의 모음)상에 존재하는 모든 노드.
• 자손(후손, descendant) 노드 - 어떤 노드 X에서 단말 노드까지의 경로상에 존재하는 모든 노드.
• 레벨(level) - 루트 노드로부터 특정 노드까지의 거리(루트 노드로부터 특정 노드까지의 가지의 개수).
루트 노드 = 레벨 0.
루트의 자식 노드 = 레벨 1
루트 노드의 자식 노드의 자식 노드 = 레벨이 2
형제 노드들은 반드시 같은 레벨에 존재
같은 레벨에 있는 모든 노드가 형제 노드는 아님.

• 트리의 깊이(depth) / 높이(height) - 루트 노드로부터 가장 긴 경로있는 단말 노드의 레벨에 1의 값을 더한 것.

• 서브트리(subtree) - 특정 노드를 루트 노드로 하여 아래에 있는 연결된 구조를 의미.
• 서브트리의 첫 번째 노드 - 해당 서브트리의 루트 노드.
• 숲(forest) - n개의 서브트리를 가진 트리에서 루트 노드를 제거해서 얻을 수 있는 분리된 서브트리의 집합.