트리 이론 편집하기

'''트리 이론'''(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))
==코드 예제==
아래는 이진 트리의 순회 예제이다.<syntaxhighlight lang="python">
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)
</syntaxhighlight>
 출력 결과 예시:
  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.