트리 (Tree)의 개념 및 구현

트리(Tree) 자료구조는 계층적이고 비선형적인 구조로 데이터를 표현하는데 유용한 자료구조입니다.
그래프의 한 형태로, 서로 연결된 노드들로 구성된 트리는 많은 응용 분야에서 사용되며, 대표적인 예로 파일 시스템, 데이터베이스, 컴파일러 등이 있습니다.
이번 포스팅에서는 트리의 개념과 이를 C#으로 구현하는 방법에 대해 알아보겠습니다.

---

1. 트리란?

트리는 계층적 구조를 가지며 부모-자식 관계로 구성된 노드들의 집합입니다. 트리의 최상위 노드는 루트(Root)라 불리며, 루트에서 출발하여 하위 노드들(자식)로 내려갑니다. 일반적으로 트리는 여러 노드를 가질 수 있고, 노드의 개수가 많을수록 트리의 크기가 커집니다.

1.1 트리의 기본 용어

• 루트 노드 (Root Node): 트리의 최상위 노드
• 부모 노드 (Parent Node): 특정 노드와 직접 연결된 상위 노드
• 자식 노드 (Child Node): 특정 노드와 직접 연결된 하위 노드
• 잎 노드 (Leaf Node): 자식이 없는 노드
• 깊이 (Depth): 루트 노드에서 특정 노드까지의 거리
• 레벨 (Level): 트리에서 같은 깊이를 가진 노드들 집합
• 높이 (Height): 루트에서 가장 멀리 있는 잎 노드까지의 거리

1.2 트리의 특성

트리는 사이클이 없는 비순환 구조이며, 하나의 루트에서 출발하여 다른 모든 노드로 향하는 유일한 경로가 존재합니다. 각 자식 노드는 오직 하나의 부모만 가질 수 있어야 합니다.

---

2. 트리의 종류

트리는 여러 종류가 있으며, 각각의 트리들은 특정한 규칙에 따라 구조가 달라집니다:

1. 이진 트리(Binary Tree): 각 노드는 최대 두 개의 자식을 가집니다.
2. 이진 탐색 트리(Binary Search Tree, BST): 왼쪽 자식은 부모보다 작은 값을, 오른쪽 자식은 부모보다 큰 값을 가집니다.
3. 균형 트리(AVL 트리, 레드-블랙 트리): 노드 삽입 및 삭제 시 균형을 유지하여 트리의 높이를 낮춥니다.
4. B 트리 및 B+ 트리: 데이터베이스와 파일 시스템에서 자주 사용되는 구조입니다.

---

3. 트리의 구현 (C# 예제)

여기서는 가장 간단한 트리 형태를 구현하고, 기본적인 삽입과 탐색 연산을 포함한 구조를 살펴보겠습니다.

3.1 트리 노드 클래스 구현

노드는 데이터와 자식 노드를 포함하는 구조로 정의됩니다. 각 노드는 자신의 데이터와 하위 자식 노드에 대한 정보를 가지고 있습니다.

public class TreeNode
{
    public int Data;
    public List<TreeNode> Children;

    public TreeNode(int data)
    {
        Data = data;
        Children = new List<TreeNode>();
    }

    public void AddChild(TreeNode child)
    {
        Children.Add(child);
    }
}

3.2 트리 클래스 구현

다음으로는 트리 클래스와 주요 기능을 구현해 봅시다. 트리 클래스는 루트 노드를 포함하며, 노드를 삽입하고 트리를 순회하는 기능을 가질 수 있습니다.

using System;
using System.Collections.Generic;

public class Tree
{
    public TreeNode Root;

    public Tree(int rootData)
    {
        Root = new TreeNode(rootData);
    }

    // DFS (Depth-First Search) 방식으로 트리 순회
    public void TraverseDFS(TreeNode node)
    {
        if (node == null) return;

        Console.WriteLine(node.Data);  // 방문한 노드의 데이터 출력
        foreach (var child in node.Children)
        {
            TraverseDFS(child);  // 재귀적으로 자식 노드 탐색
        }
    }

    // BFS (Breadth-First Search) 방식으로 트리 순회
    public void TraverseBFS()
    {
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(Root);

        while (queue.Count > 0)
        {
            var node = queue.Dequeue();
            Console.WriteLine(node.Data);  // 방문한 노드의 데이터 출력

            foreach (var child in node.Children)
            {
                queue.Enqueue(child);
            }
        }
    }
}

3.3 트리 사용 예시

public class Program
{
    public static void Main()
    {
        // 트리 생성 및 노드 추가
        Tree tree = new Tree(1);  // 루트 노드 생성
        tree.Root.AddChild(new TreeNode(2));
        tree.Root.AddChild(new TreeNode(3));
        tree.Root.Children[0].AddChild(new TreeNode(4));
        tree.Root.Children[0].AddChild(new TreeNode(5));
        tree.Root.Children[1].AddChild(new TreeNode(6));

        Console.WriteLine("DFS Traversal:");
        tree.TraverseDFS(tree.Root);  // 출력: 1 2 4 5 3 6

        Console.WriteLine("\nBFS Traversal:");
        tree.TraverseBFS();  // 출력: 1 2 3 4 5 6
    }
}

코드 설명

• TraverseDFS: 깊이 우선 탐색 방식으로 트리를 순회하며 모든 노드를 방문합니다. 루트 노드에서 시작하여 자식 노드를 재귀적으로 탐색합니다.
• TraverseBFS: 너비 우선 탐색 방식으로 트리를 순회합니다. 큐를 사용하여 같은 레벨의 모든 노드를 차례로 방문합니다.

---

4. 트리의 장단점

장점

• 계층적 데이터 표현: 트리는 계층적 구조로 데이터를 표현하는 데 유리합니다.
• 탐색 효율성: 특히 이진 탐색 트리, AVL 트리와 같은 트리 구조에서는 탐색, 삽입, 삭제 연산의 효율이 뛰어납니다.

단점

• 복잡한 구조: 트리의 구조가 복잡해질수록 구현 및 유지보수가 어려워질 수 있습니다.
• 불균형 가능성: 단순 이진 탐색 트리의 경우 데이터 삽입 순서에 따라 트리가 한쪽으로 치우칠 수 있습니다.

---

트리는 계층적 데이터 구조로서, 많은 컴퓨터 과학 및 엔지니어링 문제에 적합한 자료구조입니다.