IT용어위키

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

정의

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

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

트리의 종류

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

루트 트리(Rooted Tree)

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

이진 트리(Binary Tree)

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

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

스패닝 트리(Spanning Tree)

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

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

K-진 트리(K-ary Tree)

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

트리의 표현 방법

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

부모 배열(Parent Array)

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

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

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

인접 리스트(Adjacency List)

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

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

트리 알고리즘

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

트리 순회(Tree Traversal)

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

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

트리 검색(Tree Search)

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

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

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

코드 예제

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

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

응용

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

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

같이 보기

참고 문헌

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.