트리 이론

트리 이론(Tree Theory)은 그래프 이론의 하위 분야로, 트리(Tree)라는 특정한 유형의 그래프를 연구하는 학문이다. 트리는 사이클이 없는 연결 그래프이며, 데이터 구조 및 알고리즘에서 중요한 역할을 한다. 트리 이론은 네트워크, 데이터베이스, 검색 알고리즘, 파일 시스템 등의 다양한 응용 분야에서 활용된다.

1 정의

트리는 사이클이 없는 연결 그래프로, 다음과 같은 성질을 만족한다.

• 노드(V)와 간선(E) 사이의 관계 → V개의 노드를 가지는 트리는 항상 V-1개의 간선을 가진다.
• 유일한 경로 → 두 노드 간의 경로가 항상 유일해야 한다.
• 사이클이 없음 → 어떤 노드에서 출발해 방향을 따라가도 다시 같은 노드로 돌아오는 경로(순환, Cycle)가 존재하지 않는다.

2 트리의 종류

트리는 다양한 유형으로 분류된다.

2.1 루트 트리(Rooted Tree)

특정한 노드를 루트(Root)로 지정한 트리. 예: 이진 트리, AVL 트리, B-트리

2.2 이진 트리(Binary Tree)

각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리.

• 이진 탐색 트리(BST) → 왼쪽 서브트리는 작은 값, 오른쪽 서브트리는 큰 값을 가짐
• 균형 트리(Balanced Tree) → AVL 트리, 레드-블랙 트리(RB Tree) 등

2.3 스패닝 트리(Spanning Tree)

주어진 그래프에서 최소한의 간선만 포함하여 모든 노드를 연결하는 트리.

• 최소 신장 트리(MST, Minimum Spanning Tree) → 크루스칼 알고리즘, 프림 알고리즘으로 찾을 수 있음

2.4 K-진 트리(K-ary Tree)

각 노드가 최대 K개의 자식을 가질 수 있는 트리. 예: 3진 트리(Ternary Tree), 4진 트리(Quaternary Tree)

3 트리의 표현 방법

트리는 여러 방식으로 표현할 수 있다.

3.1 부모 배열(Parent Array)

각 노드의 부모를 배열로 나타냄.

노드:   0  1  2  3  4  5  
부모:  -1  0  0  1  1  2  

0번 노드는 루트(-1), 1번과 2번은 0번의 자식.

3.2 인접 리스트(Adjacency List)

각 노드마다 자식 노드 목록을 저장.

0: [1, 2]  
1: [3, 4]  
2: [5]  
3: []  
4: []  
5: []  

4 트리 알고리즘

트리에서는 다양한 알고리즘이 사용된다.

4.1 트리 순회(Tree Traversal)

트리의 모든 노드를 특정한 순서로 방문하는 알고리즘.

• 전위 순회(Preorder) → 루트 → 왼쪽 → 오른쪽
• 중위 순회(Inorder) → 왼쪽 → 루트 → 오른쪽
• 후위 순회(Postorder) → 왼쪽 → 오른쪽 → 루트
• 레벨 순회(Level Order) → BFS 방식

4.2 트리 검색(Tree Search)

• 이진 탐색 트리(BST)에서 특정 값 찾기 (O(log N))
• 트라이(Trie) → 문자열 탐색에 사용

4.3 최소 신장 트리(MST, Minimum Spanning Tree)

• 크루스칼 알고리즘 (O(E log E))
• 프림 알고리즘 (O((V+E) log V))

5 코드 예제

아래는 이진 트리의 순회 예제이다.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value, end=" ")
        inorder_traversal(node.right)

# 트리 생성
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# 중위 순회 실행
inorder_traversal(root)

출력 결과 예시:
 4 2 5 1 3  

6 응용

트리는 다양한 분야에서 활용된다.

• 컴퓨터 과학 → 데이터 구조 (BST, AVL, B-트리)
• 파일 시스템 → 디렉토리 구조
• 네트워크 → 라우팅 트리
• 인공지능 → 의사결정 트리(Decision Tree)
• 문자열 탐색 → 트라이(Trie) 사용

7 같이 보기

• 그래프 이론
• 이진 탐색 트리
• 최소 신장 트리
• 트라이 (자료 구조)

8 참고 문헌

• Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.
• Knuth, Donald E. "The Art of Computer Programming, Volume 1: Fundamental Algorithms." Addison-Wesley, 1997.