トライ木（接頭辞木）とは？仕組み・コード・計算量を解説

トライ木が解決する問題

ハッシュセットは「この単語は正確に格納されているか？」にはすばやく答えられますが、「preで始まる格納済みの単語はどれか？」には、すべての単語を調べない限り答えられません。ソート済みリストなら二分探索で接頭辞クエリに答えられますが、挿入が遅くなります。トライ木は接頭辞で構成されているので、接頭辞に関する問いが本来の強みです。検索ボックスのオートコンプリート、言葉遊びのゲーム、スペルチェック、ネットワーク経路の最長一致検索などです。

イメージで理解する

スマホの連絡先リストを、1文字ずつ絞り込んでいく場面を考えてください。cと入力するとcで始まる人がすべて表示され、caと入力すると絞り込まれ、と続きます。トライ木は、単語をまさにこの形で格納します。根は空の接頭辞です。各ノードは、次の文字から子ノードへのマップと、単語の終端フラグを持ちます。carのような単語は、完全な単語であると同時にcartの接頭辞でもありうるからです。

具体例：car、cart、cat、dogの挿入

4つの単語は合計13文字ですが、car、cart、catがcaを共有するため、根より下に必要なノードは8個（c, a, r, t, t, d, o, g）だけです。caを検索すると2つのノードをたどり、接頭辞としては成功しますが、そのノードには終端が付いていないので、caは単語ではありません。cowを検索すると、2ステップ目で失敗します。ノードcにはoの子がないからです。

Pythonでの実装

各ノードは子のdictを持つので、Unicodeを含むどんな文字集合も扱えます。starts_withメソッドは、接頭辞の下にあるすべての単語を集めます。これがオートコンプリートの中核です。

class TrieNode:
    __slots__ = ("children", "is_word")
    def __init__(self):
        self.children = {}
        self.is_word = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True
    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node
    def contains(self, word):
        node = self._find(word)
        return node is not None and node.is_word
    def starts_with(self, prefix):
        node, out = self._find(prefix), []
        stack = [(node, prefix)] if node else []
        while stack:
            node, path = stack.pop()
            if node.is_word:
                out.append(path)
            for ch, child in node.children.items():
                stack.append((child, path + ch))
        return sorted(out)

t = Trie()
for w in ["car", "cart", "cat", "dog"]:
    t.insert(w)
print(t.contains("car"), t.contains("ca"))  # True False
print(t.starts_with("ca"))                  # ['car', 'cart', 'cat']
print(t.starts_with("x"))                   # []

starts_withは、出力順を安定させるためにソートしています。実際のオートコンプリートでは、最初の数件で打ち切り、たとえば格納した人気度のカウントで順位付けもします。

時間計算量と空間計算量

時間は単語の数nに依存しません。これが、文字列の平衡木（O(m log n)回の比較）に対する主な利点です。代償はメモリです。各ノードはそれぞれ辞書を持つ別のオブジェクトなので、トライ木は元の文字列の何倍ものメモリを使うことがあります。

種類と、よくある間違い

• 配列による子：小文字の英語なら、26スロットの固定配列を使います。dictより高速ですが、疎な文字集合や大きな文字集合では無駄が出ます。
• 圧縮トライ（基数木、Patriciaトライ）：子が1つだけのノードの連なりを、文字列でラベル付けした1本の辺にまとめ、メモリを大きく節約します。基数木は、IPルーティングテーブルや一部のHTTPルーターで使われています。
• 三分探索木：各ノードが3つの子（小さい、等しい、大きい）を持ち、幅広い配列よりメモリが少なくて済みます。
• カウント付きトライ：各ノードにカウンタを持たせ、「この接頭辞で始まる単語はいくつあるか？」にO(m)で答えます。
• ビット単位のトライ：数値を1ビットずつ格納し、最大XORの問題を解きます。

トライ木を使う場面と、面接でよく出る問題

接頭辞クエリ、最長一致検索、または接頭辞を共有する多数の文字列の順序付き反復が必要なときに、トライ木を使います。完全一致の検索だけなら、setやdictを使います。Pythonではそのほうが単純で、メモリも少なくて済みます。小規模で静的な単語リストなら、bisectモジュールとソート済みリストでも、接頭辞クエリにうまく答えられます。

よく出る問題：トライ木の実装（insert、search、starts-with）、多数の目標単語を使ったグリッド上の単語検索、単語を最短の語根に置き換える、最長共通接頭辞、検索オートコンプリートシステムの設計、ビット単位のトライを使った2つの数の最大XORなどです。