트라이 (Trie)의 개념 및 구현

트라이(Trie)의 개념 및 구현

트라이(Trie)는 문자열을 효율적으로 저장하고 탐색하기 위해 사용되는 트리 기반 자료구조입니다.
주로 문자열 검색과 패턴 매칭에서 활용되며, 특히 사전(Dictionary) 데이터와 같이 많은 문자열을 처리해야 하는 상황에서 뛰어난 성능을 발휘합니다. 이번 포스팅에서는 트라이의 개념, 특징, 구현 방법, 그리고 활용 사례를 살펴보겠습니다.

---

1. 트라이(Trie)란?

1.1 정의

• 트라이는 문자열 집합을 저장하고 탐색하는 데 최적화된 트리 자료구조입니다.
• 각 노드는 문자 하나를 나타내며, 경로를 따라 이동하면 문자열이 형성됩니다.
• 루트 노드는 빈 상태로 시작하며, 문자열의 끝을 나타내는 노드에 별도의 표시(예: isEnd)를 추가합니다.

1.2 주요 특징

• 문자열 삽입 및 검색의 시간 복잡도: O(L), 여기서 L은 문자열의 길이.
• 공통 접두사를 공유하여 저장 공간 절약.
• 문자열의 빠른 검색과 자동 완성 기능 지원.

---

2. 트라이의 구조

트라이의 기본 구성 요소는 다음과 같습니다:

• 노드(Node): 각 노드는 특정 문자를 저장하며, 자식 노드를 가집니다.
• isEnd: 문자열의 끝을 나타내는 플래그.
• 자식 포인터(Children): 자식 노드를 가리키는 데이터 구조(대개 배열, 맵, 또는 딕셔너리).

---

3. 트라이의 주요 연산

3.1 삽입 (Insert)

1. 루트 노드에서 시작합니다.
2. 문자열의 각 문자를 하나씩 트리를 따라가며 노드가 없으면 생성합니다.
3. 문자열의 마지막 문자에서 isEnd를 true로 설정합니다.

3.2 검색 (Search)

1. 루트 노드에서 시작합니다.
2. 문자열의 각 문자를 따라 트리를 탐색합니다.
3. 문자열의 끝에 도달했을 때 해당 노드의 isEnd가 true이면 문자열이 존재합니다.

3.3 삭제 (Delete)

1. 문자열의 노드를 역순으로 탐색하며 isEnd와 자식 노드를 확인합니다.
2. 문자열이 더 이상 필요 없으면 해당 노드를 삭제합니다.

---

4. C#으로 트라이 구현

아래는 C#을 사용한 기본 트라이 자료구조의 구현 예제입니다:

using System;
using System.Collections.Generic;

public class TrieNode
{
    public Dictionary<char, TrieNode> Children { get; private set; }
    public bool IsEnd { get; set; }

    public TrieNode()
    {
        Children = new Dictionary<char, TrieNode>();
        IsEnd = false;
    }
}

public class Trie
{
    private TrieNode root;

    public Trie()
    {
        root = new TrieNode();
    }

    // 문자열 삽입
    public void Insert(string word)
    {
        var current = root;
        foreach (char c in word)
        {
            if (!current.Children.ContainsKey(c))
            {
                current.Children[c] = new TrieNode();
            }
            current = current.Children[c];
        }
        current.IsEnd = true;
    }

    // 문자열 검색
    public bool Search(string word)
    {
        var current = root;
        foreach (char c in word)
        {
            if (!current.Children.ContainsKey(c))
                return false;
            current = current.Children[c];
        }
        return current.IsEnd;
    }

    // 접두사 검색
    public bool StartsWith(string prefix)
    {
        var current = root;
        foreach (char c in prefix)
        {
            if (!current.Children.ContainsKey(c))
                return false;
            current = current.Children[c];
        }
        return true;
    }
}

// 사용 예제
public class Program
{
    public static void Main()
    {
        Trie trie = new Trie();

        trie.Insert("apple");
        trie.Insert("app");

        Console.WriteLine(trie.Search("app"));    // true
        Console.WriteLine(trie.Search("apple"));  // true
        Console.WriteLine(trie.Search("appl"));   // false
        Console.WriteLine(trie.StartsWith("ap")); // true
    }
}

---

5. 트라이의 활용 사례

1. 자동 완성 (Autocomplete)
   • 사용자가 입력한 접두사를 기반으로 추천 단어를 검색합니다.
   • 예: 검색 엔진, IDE의 코드 완성.
2. 단어 사전(Dictionary) 구현
   • 단어와 빈도 데이터를 효율적으로 관리.
3. 문자열 패턴 매칭
   • 문자열에서 특정 패턴 검색.
   • 예: Spam 필터, DNA 서열 분석.
4. 접두사 문제 해결
   • 특정 접두사를 가진 문자열 집합 검색.
5. IP 주소 및 네트워크 라우팅
   • IP 주소를 트리 형태로 저장하고 빠르게 검색.

---

6. 트라이의 장단점

6.1 장점

• 빠른 문자열 검색: O(L)의 시간 복잡도.
• 공간 절약: 공통 접두사를 공유.
• 다양한 응용: 자동 완성, 패턴 매칭 등에서 활용 가능.

6.2 단점

• 공간 소비: 노드가 많아질수록 메모리 사용량 증가.
• 구현의 복잡성.

---

트라이는 문자열을 효율적으로 처리하기 위한 강력한 자료구조로, 특히 검색과 패턴 매칭에 강점이 있습니다.