trie(prefix tree)란 무엇이며, 언제 유용한가요?

Question

Accepted Answer

**trie(트라이, prefix tree, 접두사 트리)**는 각 **간선**이 하나의 문자를 나타내고, 루트로부터의 각 **경로**가 하나의 접두사를 이루는 트리입니다. 접두사를 공유하는 단어들은 같은 경로를 공유하므로, 접두사 조회가 극도로 빠릅니다.

## 구조

```text
"cat", "car", "dog" 삽입:
        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t*  r*   g*       (* 는 단어의 끝을 표시)
```

## 코드

```python
class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):           # O(L), L = 단어 길이
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True
    def starts_with(self, prefix):    # O(L)
        node = self.root
        for ch in prefix:
            if ch not in node.children: return False
            node = node.children[ch]
        return True
```

## 복잡도

| 연산 | 시간 |
|---|---|
| 삽입 | O(L) |
| 검색 | O(L) |
| 접두사 질의 | O(L) |

결정적으로, 비용은 저장된 단어의 *개수*가 아니라 **단어 길이 L**에 따라 결정됩니다.

## 트레이드오프

- **강점:** 빠른 접두사 검색; 자동완성; 유사한 단어들이 접두사를 공유하여 공간 절약.
- **약점:** 노드마다 높은 메모리 오버헤드(각 노드가 자식 맵을 가짐); 무관한 key에 대해서는 hash set보다 더 많은 공간을 쓸 수 있음.

## 왜 중요한가

trie는 **접두사** 매칭이 중요한 자동완성, 맞춤법 검사기, IP 라우팅 테이블, 사전 기반 검색을 구동합니다.

hash set이 "정확한 일치"만 답할 때, trie는 추가로 "X로 시작하는 단어는 무엇인가?"를 효율적으로 답합니다.