[CS] 자료구조 - 트리

트리(Tree)

- 데이터 간의 관계를 나타내는 비선형 자료구조

- 노드(node) 라고 불리는 부분과 노드를 연결하는 가지(branch, edge)로 구분됨

- 노드 사이에는 계층적인 관계성을 갖음

 

 

# 트리 용어 정의

• 노드(node) : 정보 항목을 의미
• 루트(root) : 빈 트리가 아닌 경우에 맨 꼭대기에 있는 하나의 노드
• 차수(degree) : 각 노드에 있는 가지의 수
• 잎 노드(leaf node) = 단말 노드(terminal node) : 노드의 차수가 0인 노드
• 내부 노드 = 비단말 노드(non-terminal node) : 루트 노드와 단말 노드를 제외한 나머지 노드
• 부모(조상) 노드 : 루트 노드로부터 어떤 노드 x까지의 경로(가지들의 모음) 상에 존재하는 모든 노드를 x의 부모 노드라고 함
• 자식(자손) 노드 : 어떤 노드 X에서 단말 노드까지의 경로 상에 존재하는 모든 노드를 자식 노드라고 함
• 레벨(level) : 루트 노드로부터 거리(가지의 수)를 의미
• 트리의 깊이(depth)/높이(height) : 루트 노드로부터 가장 긴 경로에 있는 단말 노드의 레벨이 1의 값을 더한 것
• 서브 트리(subtree) : 특정 노드를 루트 노드로 하고, 그 아래에 있는 연결된 구조의 트리
• 숲(forest) : n개의 서브 트리를 가진 트리에서 루트 노드를 제거해서 얻을 수 있는 분리된 서브 트리의 집합