[자료구조] 트리 (Tree)

트리 구조와 트리 종류에 대한 설명입니다.

---

1. 트리란?

트리는 노드로 이루어진 자료 구조이다.

트리 구조

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
• 내부(internal) 노드: 단말 노드가 아닌 노드
• 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
• 형제(sibling): 같은 부모를 가지는 노드
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

2. 트리의 특징

• 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류
• 노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
  즉, 간선은 항상 (정점의 개수 - 1) 만큼을 가진다.
• 루트에서 어떤 노드로 가는 경로는 유일하다.
  임의의 두 노드 간의 경로도 유일하다.
  즉, 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
• 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
  부모-자식 관계이므로 흐름은 top-bottom 아니면 bottom-top으로 이루어진다.

3. 트리(Tree)의 종류

일반 트리와 이진트리로 분류할 수 있다.

• 일반 트리
  
  하나의 부모에 여러개의 자식이 존재할 수 있다.

일반 트리 구조

•  이진트리 (Binary Tree)
  
  노드마다 0-2개의 자식만 가질 수 있다.

 

이진 트리 구조

4. 이진 트리의 종류

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

항상 2개의 자식을 가진다.
마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며,
마지막 레벨의 모든 노드는 가능한 한 왼쪽부터 있다.
마지막 레벨 h에서 1부터 2h-1개의 노드를 가진다.

완전 이진 트리 구조

2) 균형 이진 트리 (Balanced Binary Tree)

 모든 노드의 왼쪽과 오른쪽의 하위 트리와의 높이가 1 이상 차이가 나지 않는 이진 트리 구조이다.

3) 변질 트리 (Degenerate Tree)

각 부모 노드는 오직 한 개의 연관 자식 노드를 갖는다.

이는 성능 면에서 트리가 연결 리스트 데이터 구조처럼 동작한다는 것을 의미한다.

변질 트리 구조