この記事で伝えること

検索フォームに文字を打ち込むと、瞬時に候補が出てくる「入力補完（オートコンプリート）」を見たことがない人はいないと思います。あの裏側で活躍しているデータ構造の1つが**トライ木（Trie）**です。

この記事では、

トライ木がどんな構造をしているのか
なぜ文字列検索・前方一致検索が高速なのか
ハッシュテーブルや二分探索木と何が違うのか
Pythonでの簡単な実装例

を、丁寧に解説していきます。読み終える頃には「なるほど、辞書アプリや検索エンジンがなぜあんなに速いのか」が腑に落ちるはずです。

トライ木とは何か

トライ（Trie）という名前は「retrieval（検索）」から来ています。木構造の一種で、1つのノードが1文字を表し、根からノードをたどっていくと1つの単語ができあがるという特徴を持っています。

たとえば cat, car, dog という3つの単語を格納したトライ木は、次のような構造になります。

ポイントは、cat と car が c → a という経路を共有していることです。共通の接頭辞（プレフィックス）を持つ単語同士は、木の途中まで同じ枝を通ります。これがトライ木の最大の特徴であり、名前の由来でもあります。

なぜ検索が速いのか

ハッシュテーブルや二分探索木と比較すると、トライ木の強みがはっきりします。

データ構造	完全一致検索	前方一致検索（〇〇で始まる単語）
ハッシュテーブル	O(1) 平均	全件走査が必要（苦手）
二分探索木	O(log n)	部分木を辿れば可能だが効率は限定的
トライ木	O(L)（Lは文字列長）	O(L + 該当件数) で高速

ハッシュテーブルは「この単語がまるごと存在するか」を調べるのは得意ですが、「ca で始まる単語を全部出して」という前方一致検索は苦手です。ハッシュ値は文字列全体から計算されるため、部分文字列だけでは手がかりがないからです。

一方トライ木では、ca というプレフィックスをたどってそのノードに到達した時点で、そこから下にぶら下がっている全ての単語が「ca で始まる単語」になります。木を根から c → a とたどるだけで候補の入り口にたどり着けるので、検索対象の単語数がどれだけ多くても、探索コストは入力した文字列の長さにほぼ比例します。これが入力補完のような用途でトライ木が選ばれる理由です。

Pythonでの簡単な実装

イメージを掴むために、最小限のトライ木をPythonで実装してみます。

class TrieNode:
    def __init__(self):
        self.children = {}  # 文字 -> TrieNode
        self.is_end = False  # ここで単語が終わるか


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def starts_with(self, prefix: str) -> list[str]:
        """指定したprefixで始まる単語を全て返す"""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []  # プレフィックス自体が存在しない
            node = node.children[char]

        results = []
        self._collect(node, prefix, results)
        return results

    def _collect(self, node: TrieNode, path: str, results: list[str]) -> None:
        if node.is_end:
            results.append(path)
        for char, child in node.children.items():
            self._collect(child, path + char, results)


trie = Trie()
for word in ["cat", "car", "dog", "card", "care"]:
    trie.insert(word)

print(trie.starts_with("ca"))  # ['cat', 'car', 'card', 'care']

starts_with の実装を見ると、まず insert で構築した経路を prefix の分だけ辿り、そこから先を再帰的に集めているだけなのが分かります。単語数が増えても、プレフィックスをたどる部分のコストは変わりません。

筆者の考え・所感

個人的にトライ木の面白さは、「データの持ち方を工夫するだけで、検索の質問の種類そのものを変えられる」という点にあると思っています。ハッシュテーブルは「これは存在するか？」というYes/No的な質問には最強ですが、「これで始まるものは何がある？」という質問には向いていません。データ構造を選ぶというのは、単に速度を最適化するだけでなく、そもそもどんな質問に効率よく答えられるようにするかを設計することなんだと、トライ木を学んだときに実感しました。

また、実務で「サジェスト機能」や「タグの入力補完」を実装する際、最初はDBに LIKE 'ca%' のようなクエリを投げて力技で解決しがちですが、候補数が数万件規模になってくるとレスポンスが目に見えて遅くなります。そういうときに、あらかじめメモリ上にトライ木を構築しておくアプローチを知っているかどうかで、選べる設計の幅がかなり変わると感じています。IME（かな漢字変換）やルーティングテーブルの実装（IPアドレスの最長一致検索）など、トライ木の応用範囲は思ったより広いので、一度仕組みを理解しておくと「あ、これもトライ木の考え方だ」と気づける場面が増えるはずです。

まとめ

トライ木は、共通のプレフィックスを持つ単語同士が木の枝を共有するデータ構造
ハッシュテーブルが苦手な「前方一致検索」を O(L + 該当件数) という低コストで実現できる
入力補完・IME・ルーティングテーブルなど、「プレフィックスで絞り込みたい」場面で威力を発揮する