저번에는 트리 기반 자료구조 중 Heap을 살펴봤습니다.
오늘은 트라이에 대해서 알아봅시다.

📖 1. Trie(트라이)

트라이는 문자열을 저장하고 탐색하는 데 특화된 트리 구조입니다.

여기 문자열 배열이 있습니다.

string[] words = { "apple", "app", "application", "banana" };

배열에서 "app"으로 시작하는 단어를 찾으려면 전부 다 비교를 해야 합니다.
즉, 시간 복잡도가 O(n)이 되는 겁니다.

이를 해결하기 할 수 있는 트리기반 자료구조입니다.

---

🔖 1-1. 트라이 구조

Trie는 문자 하나를 Node로 저장하는 구조를 가졌습니다.
각 노드가 문자 하나를 담고, 자식 노드들이 다음 문자를 담는 구조입니다

"app", "apple", "banana"를 저장한다고 가정해볼까요?

root
├── a
│   └── p
│       └── p (여기서 "app" 완성)
│           └── l
│               └── e (여기서 "apple" 완성)
└── b
    └── a
        └── n
            └── a
                └── n
                    └── a (여기서 "banana" 완성)

기본적으로 이런 식으로 저장이 되는 겁니다

그렇다면 같은 구조를 가진 문자열이 있다면 어떻게 될까요?
"cat", "car", "dog"로 예를 들어볼게요

Root
├── c
│   └── a
│       ├── t ("cat")
│       └── r ("car")
│
└── d
    └── o
        └── g ("dog")

공통 접두사(prefix)를 공유해서 저장합니다

트라이를 응용한다면 아이템 검색창, 자동완성 이런 부분을 구현할 수 있습니다!

---

🔖 1-2. 트라이 구현

class TrieNode
{
    public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
    public bool IsEnd = false; // 단어가 끝나는지 표시
}


class Trie
{
    private TrieNode root = new TrieNode();

    // 삽입
    public void Insert(string word)
    {
        TrieNode node = root;
        foreach (char c in word)
        {
            if (!node.Children.ContainsKey(c))
                node.Children[c] = new TrieNode();
            node = node.Children[c];
        }
        node.IsEnd = true; // 단어 끝 표시
    }

    // 탐색
    public bool Search(string word)
    {
        TrieNode node = root;
        foreach (char c in word)
        {
            if (!node.Children.ContainsKey(c)) return false;
            node = node.Children[c];
        }
        return node.IsEnd;
    }

    // 접두사 탐색 (Prefix Search)
    public bool StartsWith(string prefix)
    {
        TrieNode node = root;
        foreach (char c in prefix)
        {
            if (!node.Children.ContainsKey(c)) return false;
            node = node.Children[c];
        }
        return true; // IsEnd 상관없이 경로만 있으면 됨
    }
}

문자열을 저장하면 노드들이 Dictionary로 연결됩니다.

Trie trie = new Trie();
trie.Insert("app");
trie.Insert("apple");

trie.Search("app");       // true  → "app" 단어가 존재
trie.Search("appl");      // false → "appl" 단어는 없음
trie.StartsWith("appl");  // true  → "appl"로 시작하는 단어는 있음

🤔 1-2-1. 여기서 IsEnd는 왜 있을까요?

만약 단어의 끝을 알려주는 bool이 없다고 가정해봅시다

Trie에 card를 추가한다고 생각해볼게요

Root
└── c
    └── a
        └── r
            └── d

그러면 이런 식으로 저장이 되겠죠?

자 여기서 car 검색한다고 해봅시다
c -> a -> r

여기서 문제가 됩니다.

r이 단어 끝인지 확인할 길이 없기 때문에
car라는 단어를 저장하지 않아도 검색하면 단어가 있다고 나와버리는 현상이 생깁니다

저장된 단어 : card

검색 : car

결과 : 존재함 -> 잘못됨 🙅‍♂️

그래서 r 노드가 단어 끝인가?를 꼭 확인할 수 있도록 bool IsEnd로 꼭 확인하는 겁니다!

---

⏰ 1-3. 시간복잡도

연산	시간복잡도
삽입	O(L) - L은 문자열 길이
탐색	O(L)
접두사 탐색	O(L)

단어 개수(n)에 상관없이 문자열 길이에만 비례해서 단어가 100만 개여도 "apple" 찾는 건 5번만 이동합니다