자료구조 시리즈 8편

트리(Tree) 완전 이해하기

이전 글에서는 해시테이블(Hash Table)에 대해 알아봤습니다.
이번에는 계층적 구조를 표현하는 자료구조, 트리(Tree) 에 대해 자세히 정리해봅니다.

---

1. 트리란?

트리는 노드(Node)들이 부모-자식 관계로 연결된 비선형 자료구조입니다.

• 하나의 루트(Root) 노드에서 시작
• 부모 노드에서 여러 자식 노드로 갈라지는 구조
• 순환(Cycle)이 없는 연결 구조

---

2. 트리의 기본 용어

용어 설명

루트(Root)	트리의 시작 노드
부모(Parent)	다른 노드를 가리키는 노드
자식(Child)	부모에게 연결된 노드
리프(Leaf)	자식이 없는 노드 (끝 노드)
깊이(Depth)	루트부터 해당 노드까지의 거리
높이(Height)	트리에서 가장 긴 경로의 길이

---

3. 트리의 종류

종류 설명

이진 트리(Binary Tree)	모든 노드가 최대 2개의 자식을 가짐
이진 탐색 트리(BST)	왼쪽은 작은 값, 오른쪽은 큰 값 정렬
균형 트리(AVL, Red-Black Tree)	높이를 균형 있게 유지하는 트리
힙(Heap)	우선순위 큐에 사용되는 트리 구조
트라이(Trie)	문자열 검색에 특화된 트리

---

4. 이진 트리 기본 구조 예시 (C#)

 노드 정의

public class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

 트리 생성 및 연결

Node root = new Node(10);
root.Left = new Node(5);
root.Right = new Node(15);
root.Left.Left = new Node(3);
root.Left.Right = new Node(7);

 트리 순회 (중위 순회 Inorder)

void InorderTraversal(Node node)
{
    if (node == null) return;

    InorderTraversal(node.Left);
    Console.WriteLine(node.Value);
    InorderTraversal(node.Right);
}

// 사용
InorderTraversal(root);

---

5. 실생활 예시로 이해하기

• 트리 = 회사 조직도
  • CEO(루트) 밑에 부서장(자식), 그 밑에 팀원(자식)들이 연결됨
• 트리 = 폴더 구조
  • 폴더 안에 하위 폴더와 파일이 계층적으로 구성됨

---

6. 트리의 활용 사례

사용 예시 설명

데이터베이스 인덱싱	B-트리 기반 인덱스 사용
파일 시스템 구조	디렉터리와 파일을 트리 형태로 저장
게임 AI	트리 기반 의사결정 구조 (Decision Tree)

---

이번 글에서는 트리(Tree) 의 개념, 기본 용어, 종류, C# 코드 사용법을 정리했습니다.

• 트리는 부모-자식 관계로 데이터를 계층적으로 구성
• 다양한 트리 구조가 존재 (이진 트리, 탐색 트리, 힙 등)
• 실제 파일 시스템, 데이터베이스 인덱스 등 광범위하게 사용