자료구조: 트리 (Tree)

트리 (Tree) 자료구조 완벽 가이드

컴퓨터 과학에서 배열이나 연결 리스트와 같은 선형(Linear) 자료구조로 표현하기 힘든 계층적(Hierarchical) 데이터를 다룰 때 필수적인 트리(Tree) 자료구조에 대해 알아보겠습니다.

1. 트리(Tree)란?

트리는 정점(Node)과 간선(Edge)을 이용하여 데이터의 계층 관계를 표현하는 비선형 자료구조입니다. 나무를 거꾸로 뒤집어 놓은 모양과 비슷하다고 하여 트리라는 이름이 붙었습니다. 그래프(Graph)의 한 종류로, **“사이클(Cycle)이 없는 연결된 무방향 그래프”**라고 정의할 수 있습니다.

주요 특징

• 하나의 루트 노드(Root Node)를 갖습니다.
• 부모-자식 관계라는 계층을 형성합니다.
• 노드가 $N$개인 트리는 항상 $N-1$개의 간선(Edge)을 가집니다.
• 임의의 두 노드 간의 경로는 유일하게 존재합니다. (사이클이 없음)

2. 트리의 구성 요소 및 용어

트리와 관련된 용어는 코딩 테스트나 인터뷰에서 빈번하게 등장하므로 정확한 숙지가 필요합니다.

• 노드 (Node): 트리를 구성하는 기본 요소 (데이터를 담고 있음).
• 루트 (Root Node): 트리 최상단에 있는 부모가 없는 노드. 트리의 시작점.
• 간선 (Edge): 노드와 노드를 연결하는 선 (부모와 자식 간의 연결).
• 부모 노드 (Parent Node): 특정 노드의 한 단계 상위 노드.
• 자식 노드 (Child Node): 특정 노드의 한 단계 하위 노드.
• 형제 노드 (Sibling Node): 같은 부모를 공유하는 노드들.
• 리프 노드 (Leaf Node / Terminal Node): 자식 노드가 없는 트리 맨 끝의 노드.
• 내부 노드 (Internal Node): 자식을 하나라도 가지고 있는 노드 (리프 노드가 아닌 노드).
• 깊이 (Depth): 루트 노드에서 특정 노드까지 도달하기 위해 거쳐야 하는 간선의 수. (루트의 깊이는 0 또는 1로 정의함)
• 레벨 (Level): 트리의 특정 깊이를 가지는 노드들의 집합. (루트 노드가 Level 0 또는 1)
• 높이 (Height): 특정 노드에서 가장 깊은 리프 노드까지의 가장 긴 경로(간선의 수). 트리의 높이는 루트 노드의 높이와 같습니다.
• 서브 트리 (Subtree): 전체 트리의 일부분으로, 특정 노드와 그 노드의 모든 자손들로 이루어진 트리.

3. 대표적인 트리의 종류

트리는 자식 노드의 개수나 구성 형태에 따라 여러 가지로 분류됩니다. 가장 대표적인 것은 **이진 트리(Binary Tree)**입니다.

1) 이진 트리 (Binary Tree)

모든 노드가 최대 2개(0, 1, 2)의 자식 노드만 가질 수 있는 트리입니다. 왼쪽 자식(Left Child)과 오른쪽 자식(Right Child)으로 명확히 구분됩니다.

• 포화 이진 트리 (Perfect BT): 모든 내부 노드가 2개의 자식을 가지며, 모든 리프 노드가 같은 레벨에 있는 꽉 찬 트리.
• 완전 이진 트리 (Complete BT): 위에서 아래로, 왼쪽에서 오른쪽으로 빈틈없이 노드가 채워진 트리. (힙, 힙 정렬의 기반)
• 편향 이진 트리 (Skewed BT): 한쪽 방향으로만 자식을 가지는 트리 (마치 연결 리스트와 같은 선형 형태). 검색 효율이 매우 떨어집니다.

2) 이진 탐색 트리 (BST, Binary Search Tree)

이진 트리에 ‘데이터 정렬’이라는 규칙을 추가하여 탐색 효율을 극대화한 트리입니다.

• 규칙: 어떤 노드 $N$을 기준으로, 왼쪽 서브 트리에 있는 모든 노드의 값은 $N$보다 작고, 오른쪽 서브 트리에 있는 모든 노드의 값은 $N$보다 큽니다.
• 장점: 평균적으로 탐색, 삽입, 삭제의 시간 복잡도가 $O(\log N)$으로 매우 빠릅니다.
• 단점: 트리가 한쪽으로 치우친 편향 트리가 될 경우, 시간 복잡도가 $O(N)$으로 악화됩니다. 이를 해결하기 위해 스스로 균형을 맞추는 AVL 트리, Red-Black 트리 등이 존재합니다.

4. 트리 순회 (Tree Traversal)

트리의 모든 노드를 중복 없이 한 번씩 방문하는 과정을 ‘순회’라고 합니다. 이진 트리의 대표적인 순회 방법 3가지는 ‘루트 노드’를 언제 방문하느냐에 따라 이름이 결정됩니다. (항상 왼쪽을 오른쪽보다 먼저 방문합니다)

1. 전위 순회 (Pre-order): 루트 → 왼쪽 서브 트리 → 오른쪽 서브 트리
2. 중위 순회 (In-order): 왼쪽 서브 트리 → 루트 → 오른쪽 서브 트리
   • 특징: 이진 탐색 트리(BST)를 중위 순회하면 데이터를 오름차순으로 정렬된 상태로 얻을 수 있습니다.
3. 후위 순회 (Post-order): 왼쪽 서브 트리 → 오른쪽 서브 트리 → 루트

추가로 레벨 순서대로 방문하는 레벨 순회(Level-order)가 있으며, 이는 큐(Queue)를 이용한 BFS 탐색과 동일합니다.

5. 트리의 활용 사례

1. 계층적 데이터 관리: 파일 시스템(디렉터리 구조), 조직도, HTML의 DOM 구조.
2. 데이터베이스 인덱싱: B-Tree, B+Tree는 데이터베이스의 빠른 검색을 위한 인덱스 구조로 널리 사용됩니다.
3. 검색 및 정렬: 이진 탐색 트리(BST)를 통한 빠른 데이터 탐색. 힙(Heap) 트리와 힙 정렬.
4. 트라이 (Trie): 문자열 검색을 빠르게 하기 위한 트리 구조로, 자동 완성이나 검색어 추천 등에 사용됩니다.
5. 의사결정 트리 (Decision Tree): 머신러닝에서 분류(Classification)나 회귀(Regression) 문제 해결에 사용되는 예측 모델.

요약

트리(Tree)는 계층적인 데이터를 표현하고 관리하는 데 있어 가장 강력한 구조입니다. 선형 구조(배열, 연결 리스트)의 한계를 극복하고 빠른 탐색($O(\log N)$)을 가능하게 합니다. 노드, 간선, 깊이, 높이 등의 기본 용어를 정확히 이해하고, 이진 탐색 트리(BST)의 특성 및 삽입/삭제 원리를 명확히 아는 것이 인터뷰 준비의 핵심입니다.