トライ（接頭辞木）とは何か、またどのような場合に有用か？

Question

Accepted Answer

**トライ**（接頭辞木）は、各**辺**が文字を表し、**ルートからのパス**が接頭辞を綴る木です。接頭辞を共有する単語は同じパスを共有するため、接頭辞検索が非常に高速になります。

## 構造

```text
Insert "cat", "car", "dog":
        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t*  r*   g*       (* marks end-of-word)
```

## コード

```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 = word length
        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**に依存し、保存されている単語の数には依存しません。

## トレードオフ

- **長所：** 高速な接頭辞検索；オートコンプリート；類似する単語の場合、共有される接頭辞がスペースを節約する。
- **短所：** ノードあたりのメモリオーバーヘッドが大きい（各ノードが子マップを持つ）；関連性のないキーの場合、ハッシュセットより多くのスペースを使用する可能性がある。

## なぜ重要なのか

トライはオートコンプリート、スペルチェッカー、IP ルーティングテーブル、**接頭辞**マッチングが重要な辞書ベースの検索を支えています。

ハッシュセットが「完全一致」のみに答える場合、トライは「X で始まる単語は何か？」に効率的に答えます。