[자료구조] Tree (2): 트리 관련 용어 정리

트리는 단순한 노드의 집합이 아니라, 각 노드들이 서로 계층적 관계를 가지며 연결된 복합적인 자료구조이다. 트리 구조를 정확히 이해하기 위해서는 그 안에서 사용되는 주요 용어들을 확실히 알고 넘어가는 것이 중요하다.

 

이번 글에서는 트리 구조를 설명할 때 반드시 알아야 할 핵심 용어들을 정리하고, 시각 자료를 함께 활용하여 개념을 쉽게 이해할 수 있도록 하였다.

---

1. 루트 (Root)

• 트리에서 부모가 없는 노드를 루트라고 한다.
• 트리에는 단 하나의 루트 노드만 존재한다.
• 루트 노드는 트리 전체의 시작점이며, 일반적으로 레벨 0에 위치한다.

예시: 아래 그림에서 3 또는 A가 루트 노드이다.

---

2. 간선 (Edge)

• 노드 간의 연결선을 의미한다.
• 부모 노드와 자식 노드를 잇는 선이며, 트리에서 노드 수가 n개일 때 간선 수는 항상 n-1개이다.

---

3. 리프 (Leaf)

• 자식 노드가 없는 노드를 리프 노드 또는 말단 노드라고 한다.
• 트리의 최종 종착점에 위치하며, 보통 재귀 종료 조건으로 사용된다.

예시: E, J, K, H, I

---

4. 형제 노드 (Siblings)

• 같은 부모 노드를 공유하는 노드들을 형제 노드라고 한다.

예시: B, C, D는 A를 부모로 가지는 형제 노드이다.

---

5. 조상 노드 / 자손 노드 (Ancestor / Descendant)

• 루트에서 특정 노드까지 경로 상에 있는 모든 노드를 조상 노드(ancestor)라고 한다.
• 특정 노드에서 하위로 이어진 모든 노드를 자손 노드(descendant)라고 한다.

예시: A, C, G는 K의 조상 노드이며, K는 A의 자손 노드이다.

---

6. 레벨 (Level)

• 루트에서 특정 노드까지 경로 상에 있는 모든 노드를 조상 노드(ancenstor)라고 한다.
• 특정 노드에서 하위로 이어진 모든 노드를 자손 노드(descendant)라고 한다.

예시: A, C, G는 K의 조상 노드이며, K는 A의 자손 노드이다.

---

7. 깊이 (Depth)

• 루트에서 특정 노드까지 도달하는 간선 수를 깊이라고 한다.
• 트리 전체의 높이는 루트 기준 가장 깊은 노드까지의 길이이다.

예시: 루트만 있는 트리의 높이는 0이다.

---

8. 높이 (Height)

• 특정 노드에서 가장 깊은 리프 노드까지의 거리를 높이라고 한다.
• 트리 전체의 높이는 루트 기준 가장 깊은 노드까지의 길이이다.

예시: 루트만 있는 트리의 높이는 0이다.

---

9. 노드의 크기 (Size)

• 하나의 노드 크기는 자기 자신을 포함하여 하위 자손 노드들의 개수이다.
• 전체 트리의 크기는 루트 노드의 크기와 동일하다.

예시: C의 크기는 3 (자신 + G + H)

---

10. 경사 트리 (Skewed Tree)

• 모든 노드가 오직 한 개의 자식만 가질 때 이를 경사 트리라고 한다.
  • 왼쪽 자식만 있으면 left-skewed tree
  • 오른쪽 자식만 있으면 right-skewed tree

이러한 구조는 탐색 시 선형 리스트처럼 작동하여 성능이 떨어질 수 있다.

---

11. 차수 (Degree)

• 노드의 차수: 자식 노드의 수
• 트리의 차수: 모든 노드 중 가장 큰 차수

이진 트리는 모든 노드의 차수가 2 이하이다.

---

12. 내부 노드 (Internal Node)

• 리프가 아니면서 자식이 하나 이상 존재하는 노드.
• 루트도 자식이 있으면 내부 노드이다.

---

13. 서브트리 (Subtree)

• 어떤 노드를 루트로 하는 트리 구조 전체.
• 서브트리는 트리의 구조적 연산(탐색, 순회)에서 재귀 단위로 자주 사용된다.

---

14. 경로 (Path)

• 한 노드에서 다른 노드까지의 노드 순서열.
• 경로의 길이는 그 사이를 잇는 간선의 수로 측정한다.

---

15. 포화 이진 트리 / 완전 이진 트리

• 포화 이진 트리: 모든 노드가 0개 또는 2개의 자식을 가짐.
• 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 가득 차 있고, 마지막 레벨은 왼쪽부터 채워짐.

---

16. 균형 트리

• 모든 서브트리의 높이 차이가 제한 범위 내에 있는 트리.
• AVL 트리, Red-Black 트리 등이 대표적 예.

탐색, 삽입, 삭제에서 O(log n)을 보장하려면 균형 유지가 필수이다.

---

17. 트리 순회 방식 (Traversal Order)

트리를 방문하는 기본적인 4개지 방법이다.

순회 방식	방문 순서
전위 순회	루트 → 왼쪽 → 오른쪽
중위 순회	왼쪽 → 루트 → 오른쪽
후위 순회	왼쪽 → 오른쪽 → 루트
레벨 순서 순회	위에서 아래로, 왼쪽에서 오른쪽

 

중위 순회는 이진 탐색 트리의 정렬된 값 출력에 활용된다.

---

이번 글에서는 트리 구조를 이해하는 데 필수적인 용어들과, 이 구조를 깊이 있게 이해하고 활용하기 위해 알아두면 좋은 개념들을 함께 정리하였다. 이 용어들은 단순한 이론적 지식에 머물지 않고, 트리 기반 문제를 실제로 구현하고 해석하는 데 있어 매우 실질적인 도구로 작용한다.

 

다음 글에서는 트리틔 가장 기본 형태인 이진 트리(Binary Tree)에 대해 다룰 예정이다. 모든 노드가 최대 두 개의 자식을 갖는 구조로, 이진 탐색 트리, 힙, 균형 트리 등의 기반이 되는 핵심 개념이다. 지금까지 정리한 용어들이 자연스럽게 적용되는 구조이니, 이어서 학습해보기를 추천한다.