トライ木（Trie）入門 - 接頭辞検索とオートコンプリートを支えるデータ構造

検索ボックスに「pri」と打っただけで「printemps」「private」「principle」が候補に並ぶ。スマートフォンの予測変換が次の1文字を待たずに単語を提示してくる。ルーターが宛先IPアドレスから一瞬で転送先を決める。これらはどれも「ある文字列（や接頭辞）を持つデータが集合の中に存在するか、あるならどれか」を高速に answerする問題です。ハッシュテーブルは「完全に一致する文字列があるか」は得意ですが、「この接頭辞で始まる文字列は何か」には向きません。トライ木（Trie / prefix tree、接頭辞木）は、文字列を1文字ずつ木の枝にほどいて共有することで、この接頭辞に関する操作を文字列長に比例する時間で行えるようにしたデータ構造です。この記事では、素朴な実装から計算量の正確な議論、オートコンプリートやIPルーティングへの応用、圧縮トライという発展形まで、動くPythonコードで順に整理します。Union-Find入門やハッシュテーブル入門と同じアルゴリズム/データ構造入門シリーズの1本です。

トライが解く問題 — 接頭辞検索とオートコンプリート

トライが得意とするのは、文字列の集合に対する接頭辞ベースの問い合わせです。具体的には次のような操作をまとめて高速に扱いたい、という状況です。

ある文字列が集合に含まれているか（完全一致検索）
ある接頭辞で始まる文字列が集合に1つでもあるか（接頭辞検索）
ある接頭辞で始まる文字列を全部列挙したい（オートコンプリート）
集合に含まれる文字列を辞書式順序で列挙したい

ハッシュテーブルやsetは最初の「完全一致検索」には強い（平均O(1)）のですが、後の3つには向きません。ハッシュ値は文字列全体から計算されるため、似た文字列でも近い値になる保証がなく、「接頭辞が一致するものを探す」には結局集合の全要素を舐めるしかないからです。

具体例を挙げます。

検索エンジンやIDEの入力補完（オートコンプリート）
スマートフォンのT9・予測変換（フリック入力の候補表示）
スペルチェッカー（辞書に存在する語かどうかの判定と、近い語の提案）
ルーターのIPルーティングテーブルにおける最長prefix一致
辞書式順序での単語列挙（辞書アプリの一覧表示など）

トライは、これらすべてを「文字列を1文字ずつ木の枝としてほどき、共通する接頭辞を共有する」という単純なアイデアだけで実現します。

なお名前の由来と初出も押さえておきます。Wikipediaによれば、文字列集合を表現するトライという発想を最初に抽象的に記述したのはAxel Thue（1912年）で、計算機科学の文脈で初めて記述したのはRené de la Briandais（1959年）です。その翌年、Edward Fredkinが独立に同じ構造を記述し、論文 "Trie Memory"（Communications of the ACM 3(9), pp.490-499, 1960年）で"trie"という名前を提案しました。これは英単語 retrieval（検索）の真ん中の音節から取られています。Fredkin自身は「tree」と区別するために/tri:/（「トリー」に近い発音）と読むことを意図していましたが、Wikipediaも述べている通り、実務では/traɪ/（「トライ」、treeと区別する発音）と読む人も多く、統一されていません。

トライの構造 — ノード、子への枝、終端フラグ

トライは根（root）を持つ順序木で、次の性質を持ちます。

各枝（edge）には1文字が対応する
根から任意のノードまでの経路をたどると、その経路上の文字を順に並べた文字列が得られる
あるノードには、そのノードが表す文字列が実際に集合の要素として登録されているかを示す終端フラグ（is_end / is_word）を持たせる

最後の終端フラグが重要です。たとえば "car" と "card" の両方を登録すると、"car" に対応するノードを通過したあとにさらに "d" の枝をたどって "card" に到達します。このとき "car" のノードにも終端フラグが立っていなければ、"card" は登録したのに "car" が登録されていないという状態を正しく区別できません。

子への枝の持ち方には主に2通りの実装があります。

固定長配列: アルファベットが26文字のみなど、文字種が決まっている場合に children[26] のような配列を持たせる。添字アクセスなので定数倍が軽いが、使われない文字の分だけ配列の器が無駄になる
ハッシュマップ / 連想配列: children を辞書として持ち、実際に登場した文字だけをキーとして持たせる。Unicodeなど文字種が多い、あるいは疎な場合に有利

この記事では汎用性を優先し、dict による子ノードの実装で進めます。

素朴な実装 — 挿入・検索・接頭辞検索を動くコードで

まずは最小構成のトライを書いてみます。

class TrieNode:
    def __init__(self):
        self.children = {}      # 文字 -> 子ノード（登場した文字だけを持つ）
        self.is_end = False     # このノードで単語が終わるか
 
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word):                 # 単語を1文字ずつたどりながらノードを作る
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True                   # 最後の文字のノードに終端フラグを立てる
 
    def search(self, word):                  # 完全一致検索
        node = self._walk(word)
        return node is not None and node.is_end
 
    def starts_with(self, prefix):            # 接頭辞検索（この接頭辞で始まる単語が1つでもあるか）
        return self._walk(prefix) is not None
 
    def _walk(self, s):                       # s の経路をたどり、最後のノードを返す（無ければ None）
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node
 
 
trie = Trie()
for w in ["cat", "car", "card", "care", "dog"]:
    trie.insert(w)
 
print(trie.search("car"))         # 完全一致で登録されている
print(trie.search("ca"))          # "ca" 自体は登録されていない
print(trie.starts_with("ca"))     # "ca" で始まる単語はある（cat, car, card, care）
print(trie.starts_with("do"))     # "do" で始まる単語はある（dog）
print(trie.starts_with("x"))      # 存在しない接頭辞

実行結果は次の通りです。

True
False
True
True
False

search と starts_with の違いに注目してください。どちらも根からの経路をたどる _walk を使っていますが、search は最後に終端フラグまで確認し、starts_with は経路が存在するかだけを見ています。この「経路をたどるだけの操作」と「終端フラグまで見る操作」を分けて持てるのが、ハッシュテーブルにはないトライの強みです。

計算量 — 文字列長 L に比例する O(L) とハッシュテーブルとの違い

トライの挿入・検索・接頭辞検索は、いずれも探索対象の文字列の長さに比例する時間で終わります。Wikipediaの記法に合わせると、検索対象の文字列の長さを m（この記事では L と表記）としたとき、挿入・検索はいずれもO(L)です。集合に格納されている単語の総数 n には（各ノードでの子の探索を定数時間とみなせば）依存しません。これは木の深さが常に「探している文字列の長さ」までしかないことから来ています。

ハッシュテーブルとの違いを正確に整理します。

操作	トライ	ハッシュテーブル（平均）	ハッシュテーブル（最悪）
挿入	`O(L)`	`O(1)`（ただしハッシュ値の計算自体に`O(L)`）	`O(L)`（衝突が集中した場合）
完全一致検索	`O(L)`	`O(1)`（同上）	`O(L)`
接頭辞を持つか判定	`O(L)`	非対応（全要素走査で`O(nL)`相当）	同左
接頭辞に一致する全単語の列挙	`O(L + 出力サイズ)`	非対応	同左

見落とされがちな点として、ハッシュテーブルの「平均O(1)」は文字列のハッシュ値の計算コストを含んでいません。文字列のハッシュ値を求めるには結局その文字列を先頭から全部読む必要があり、これ自体がO(L)かかります。したがって単純な完全一致検索に限って言えば、トライのO(L)とハッシュテーブルの実質コストは大きくは変わりません。トライが真価を発揮するのは、ハッシュテーブルがそもそも対応できない接頭辞に関する操作です。

次のコードで、ハッシュ集合（set）に対して「接頭辞検索」をやろうとすると何が起きるかを見てみます。

words_set = {"cat", "car", "card", "care", "dog"}
 
def has_prefix_naive(words, prefix):
    return any(w.startswith(prefix) for w in words)   # 一致するものが無ければ最悪 O(n * L) の全走査
 
print(has_prefix_naive(words_set, "ca"))
print(has_prefix_naive(words_set, "xyz"))

True
False

set はハッシュ値による完全一致検索には最適化されていますが、接頭辞検索では結局全要素を1つずつstartswithで確認するしかありません。要素数がn個、各文字列の長さが最大Lなら最悪O(nL)です。トライのstarts_withは探している接頭辞の長さだけに依存するO(L)なので、nが大きいほど差が開きます。

空間計算量のトレードオフ

トライの空間計算量は接頭辞の共有具合に強く依存します。共通の接頭辞を持つ単語が多いほど、ノードが共有されて総ノード数が単語の総文字数より小さくなります。次のコードで実際に数えてみます。

def count_nodes(node):
    return 1 + sum(count_nodes(child) for child in node.children.values())
 
 
words = ["car", "care", "careful", "cart", "cargo"]
trie2 = Trie()
for w in words:
    trie2.insert(w)
 
total_chars = sum(len(w) for w in words)          # 全単語の文字数の単純合計
node_count = count_nodes(trie2.root) - 1           # 根を除いた実際のノード数
 
print(total_chars)
print(node_count)

23
10

5つの単語の文字数を単純に足すと23ですが、"car" という共通の接頭辞を全単語が共有しているため、実際に使われているノードは10個で済んでいます。単語どうしの接頭辞の重なりが多いデータセットほど、この圧縮効果は大きくなります。

一方で注意点もあります。子ノードを固定長配列で持つ実装（たとえばアルファベット26文字ぶんの配列）では、1ノードあたり常にO(σ)（σはアルファベットサイズ）の器を確保することになり、共有される接頭辞が少ないデータでは配列のほとんどが未使用のまま無駄になります。この記事のように子をdictで持つ実装なら、実際に登場した文字の分しか領域を使わないため、この無駄は避けられますが、その代わりハッシュマップとしての定数倍のオーバーヘッド（各エントリのキー・値・バケット管理コスト）を払うことになります。どちらの実装が有利かはデータの性質（接頭辞の共有度とアルファベットサイズ）次第というのが正確な理解です。

応用1: オートコンプリート・入力補完

接頭辞検索を一歩進めて、ある接頭辞で始まる単語を全部列挙するのがオートコンプリートの基本形です。接頭辞のノードまでたどり着いたら、そこから先を深さ優先探索（DFS）するだけで実装できます。

class AutocompleteTrie(Trie):
    def words_with_prefix(self, prefix):
        node = self._walk(prefix)
        if node is None:
            return []
        results = []
        self._collect(node, prefix, results)
        return results
 
    def _collect(self, node, path, results):
        if node.is_end:
            results.append(path)
        for ch in sorted(node.children):          # 文字順に子をたどると自然に辞書式順序で列挙できる
            self._collect(node.children[ch], path + ch, results)
 
 
ac = AutocompleteTrie()
for w in ["cat", "car", "card", "care", "careful", "dog", "do"]:
    ac.insert(w)
 
print(ac.words_with_prefix("car"))
print(ac.words_with_prefix("do"))
print(ac.words_with_prefix("z"))

['car', 'card', 'care', 'careful']
['do', 'dog']
[]

計算量は「接頭辞までたどるO(L)」＋「該当部分木を全部たどるO(該当する単語の総文字数)」です。検索ボックスの入力補完のように候補の母集団が大きくても、絞り込んだあとの候補数は少ない状況では、実用上ほぼ入力文字数だけで応答できることになります。

sorted(node.children) で子を文字順にたどっている点にも意味があります。こうするとDFSの結果が自動的に辞書式順序で得られ、あとから別途ソートし直す必要がありません。辞書アプリや索引の一覧表示のように「辞書式順序で単語を列挙したい」という要件も、このトライの性質だけでそのまま満たせます。

応用2: T9・予測変換

ガラケー時代の文字入力方式であるT9（Text on 9 keys）は、Tegic Communications（後にNuance Communicationsが買収）が開発した予測変換技術で、1つのキーを1回押すだけで、辞書と照合して最も確からしい単語を予測します。数字キー（2から9）にアルファベット数文字が割り当てられているため、同じキー列に複数の単語が対応しうるという特性があります。

この「キー列から候補の単語群を絞り込む」という処理は、接頭辞検索と同じ構造の問題です。キー列を接頭辞とみなして該当する単語を列挙し、出現頻度などでランキングして提示する、という設計はトライと非常に相性がよく、予測変換システムの実装でトライ系のデータ構造が使われることは一般的です。T9の商用実装が内部で具体的にどのデータ構造を使っているかは公開資料からは確認できておらず未確認ですが、「キー列（接頭辞）に一致する候補を高速に絞り込む」という要件自体が、まさにトライが解く問題そのものであることは明確です。現代のスマートフォンのフリック入力・予測変換でも、考え方の骨格は共通しています。

応用3: IPルーティングの最長prefix一致

IPルーティングでは、パケットの宛先アドレスに対して、ルーティングテーブルに登録された複数のネットワーク宛先（例: 10.0.0.0/8 と 10.1.0.0/16）のうち最も具体的な（プレフィックス長が長い）ものを優先して転送先を決めるという規則があります。これを最長prefix一致（Longest Prefix Match）と呼びます。

IPアドレスを2進数のビット列とみなせば、これはまさに接頭辞検索の一種です。0と1それぞれに対応する2分岐のトライ（2分トライ / binary trie）を使い、ビット列をたどりながら「経路上で最後に見つかった登録済みの終端」を覚えておけば、最長一致がそのまま求まります。

class BinaryTrieNode:
    def __init__(self):
        self.children = [None, None]   # 0 と 1 それぞれの子
        self.next_hop = None            # ここでルートが終端する場合の転送先
 
 
class LongestPrefixTrie:
    def __init__(self):
        self.root = BinaryTrieNode()
 
    def insert(self, prefix_bits, next_hop):
        node = self.root
        for bit in prefix_bits:
            idx = int(bit)
            if node.children[idx] is None:
                node.children[idx] = BinaryTrieNode()
            node = node.children[idx]
        node.next_hop = next_hop
 
    def lookup(self, address_bits):
        node = self.root
        best = None
        for bit in address_bits:
            idx = int(bit)
            if node.children[idx] is None:
                break                        # これ以上先に登録された経路は無い
            node = node.children[idx]
            if node.next_hop is not None:
                best = node.next_hop          # 経路上で最後に見つかった終端 = 最長一致
        return best
 
 
def ip_to_bits(ip, prefix_len=32):
    octets = [int(o) for o in ip.split(".")]
    bits = "".join(f"{o:08b}" for o in octets)
    return bits[:prefix_len]
 
 
routes = [
    ("10.0.0.0", 8, "if0"),
    ("10.1.0.0", 16, "if1"),
    ("10.1.2.0", 24, "if2"),
]
 
lpm = LongestPrefixTrie()
for network, plen, next_hop in routes:
    lpm.insert(ip_to_bits(network, plen), next_hop)
 
print(lpm.lookup(ip_to_bits("10.1.2.5")))       # 3つの経路すべてに合致 -> 最長の if2
print(lpm.lookup(ip_to_bits("10.1.9.9")))       # /8 と /16 に合致 -> 最長の if1
print(lpm.lookup(ip_to_bits("10.9.9.9")))       # /8 のみに合致 -> if0
print(lpm.lookup(ip_to_bits("192.168.0.1")))    # どの経路にも合致しない

if2
if1
if0
None

10.1.2.5 は 10.0.0.0/8、10.1.0.0/16、10.1.2.0/24 の全部に含まれますが、最もビット数が深い（＝プレフィックスが長い）10.1.2.0/24（if2）が採用されています。トライを深くたどるほど条件が厳しくなる（＝より具体的な経路になる）ため、「経路上で最後に見つかった終端を覚えておく」だけで最長一致が自然に求まる、という点がこの実装の肝です。

実際のインターネットルーターは経路数が数十万件に達することもあり、素朴な2分トライではメモリと段数が大きくなりすぎます。Linuxカーネルはfib_trieという実装で、経路テーブルにLC-trie（Level-Compressed trie） / LPC-trie（Level-Path-Compressed trie）と呼ばれる、パス圧縮とレベル圧縮を組み合わせた圧縮トライを採用しています。カーネルのドキュメント（Documentation/networking/fib_trie.rst）や/proc/net/fib_triestatから、実際の葉・内部ノード数や平均探索深さを確認できます。次に説明する「圧縮トライ」は、まさにこの実運用で使われている発想です。

応用4: スペルチェッカーと辞書式順序での列挙

スペルチェッカーの最も基本的な機能である「この単語は辞書に存在するか」は、searchメソッドそのものです。加えて、以下のような発展的な使い方も可能です。

タイプミスの候補提示: 入力された単語と編集距離が1〜2以内の単語を探す際、トライをDFSしながら動的計画法で編集距離の行を1行ずつ更新していくと、明らかに候補になり得ない部分木を早期に枝刈りできます（Peter Norvigのスペル訂正エッセイなど、複数の実装例が知られています）
辞書式順序での全件列挙: すでにwords_with_prefixで見た通り、子を文字順にたどるDFSだけで辞書式順序の列挙が手に入ります。空の接頭辞""で呼び出せば、集合全体を辞書式順序で列挙できます

発展1: 圧縮トライ（radix tree / PATRICIA trie）

素朴なトライの弱点は、子が1つしかないノードが鎖のように連なりやすいことです。たとえば "international" という1単語しか登録していなければ、13文字ぶんのノードが一直線に並ぶだけで、情報量に対してノード数が過剰になります。

この無駄を解消するのがradix tree（基数木）、別名圧縮トライ（compressed trie）です。Wikipediaの定義では「子を1つしか持たないノードを親と統合した、空間効率を最適化したトライの変種」とされています。PATRICIA trie（Practical Algorithm To Retrieve Information Coded In Alphanumeric）は、この考え方をビット単位の2分木に適用した具体的な実装として知られています。

素朴なトライ（"international" のみ登録）:
i -> n -> t -> e -> r -> n -> a -> t -> i -> o -> n -> a -> l  （13ノード）
 
圧縮トライ（radix tree）:
"international"                                                  （1ノード、1本の枝に文字列そのものを持つ）

複数の単語が登録されて分岐が生じた場合は、分岐点までを1本の枝にまとめます。

"car", "care", "cart" を登録した場合:
 
素朴なトライ:               圧縮トライ:
c -> a -> r -(終端)          "car"-(終端)
       |    \- e -(終端)             |- "e"-(終端)
       |    \- t -(終端)             \- "t"-(終端)

こうすることで、共有される接頭辞は素朴なトライと同じように圧縮しつつ、単独の子しか持たないノードの連鎖を1本の枝にまとめてノード数を実質的な分岐点の数まで減らせます。前述のIPルーティングでLinuxカーネルが採用しているLC-trie/LPC-trieも、このパス圧縮の考え方を土台にしています。トレードオフとして、単語の途中で分岐が挿入されると枝の文字列を分割する必要があり、実装は素朴なトライより複雑になります。

発展2: Aho-Corasickアルゴリズムとの関係

複数のパターン文字列を1回のテキスト走査で同時に検索したい場合、Aho-Corasickアルゴリズムが定番です。この記事では深入りしませんが、関係だけ簡単に触れておきます。

Aho-Corasickは、複数のパターンをまずトライにまとめて格納し、そこに「一致しなかったときにどこまで戻ればよいか」を示すサフィックスリンク（フェイル関数）を追加することで、KMP法の考え方を複数パターンに拡張したものです。テキストを1回走査するだけで、登録した全パターンの全出現位置を線形時間で列挙できます。トライは、この「複数パターンを1つの探索構造にまとめる」役割を担う土台部分にあたります。詳しい構築手順や計算量、Aho and Corasick（1975年）の原典情報は文字列検索アルゴリズム入門で扱っています。

各言語の標準ライブラリ状況

トライは実装がシンプルな一方、実際のプロダクトでは圧縮トライや省メモリ実装が求められることも多く、標準ライブラリにそのまま用意されている言語はほぼないのが実情です。2026年7月時点で確認した範囲では次の通りです。

言語	標準ライブラリ	代表的な選択肢
Python	なし（標準ライブラリに該当モジュールなし）	Google製の`pygtrie`（純粋Python、`dict`風のミュータブルなAPI）、`marisa-trie`（静的・省メモリなC++バインディング、公式ドキュメントによれば通常の`dict`より50〜100倍省メモリ）
Java	なし（`java.util`に該当クラスなし）	Apache Commons Collectionsの`PatriciaTrie`（コンパクトな接頭辞木の実装）
Go	なし（標準ライブラリに該当パッケージなし）	サードパーティ（`dghubble/trie`など）か自作
JavaScript / TypeScript	なし	npmの`@datastructures-js/trie`など。Ethereum関連では改良版の`@ethereumjs/trie`（Modified Merkle Patricia Trie）が使われる
Rust	なし（`std::collections`に該当なし）	`radix_trie`クレート、ビット単位のquad-bit popcountトライを実装する`qp-trie`クレートなど
C++	なし（STLに該当ヘッダなし。Boostにも公式収録の`boost::trie`は無い）	提案段階のBoost.Textに含まれる`trie` / `trie_map` / `trie_set`、サードパーティの`HAT-trie`など

C++については誤解しやすい点があります。Boostにはtrieという名前の入った提案ライブラリ（Boost.Text）がありますが、これは2026年7月時点でBoostの正式な公開リリースに含まれる標準コンポーネントではなく、あくまで提案・検討段階のライブラリです。「Boostにtrieがある」と断定的に書かれた記事を見かけることがありますが、正確には要確認の状態です。

Pythonで手軽に使いたい場合、pygtrieはインストールするだけでdictとほぼ同じ感覚で使えます。

import pygtrie
 
t = pygtrie.CharTrie()
t["car"] = True
t["care"] = True
t["cart"] = True
 
print(t.has_subtrie("ca"))          # "ca" を接頭辞に持つキーがあるか
print(list(t.keys(prefix="car")))   # "car" を接頭辞に持つキーの一覧

True
['car', 'care', 'cart']

Union-Findと同じく、トライも自作が現実的な選択肢になりやすいデータ構造です。基本形はTrieNodeとdictだけで数十行に収まり、用途に応じて終端フラグにカウントやメタデータを持たせるといった拡張も容易です。ただし数百万語規模の辞書や、メモリ制約の厳しい環境（組み込み機器やモバイルの予測変換辞書など）では、圧縮率の高いmarisa-trieのような専用実装に軍配が上がります。

よくある落とし穴

トライを実装・利用する際に初学者がつまずきやすいポイントを挙げます。

終端フラグを付け忘れる: "car"と"card"を両方登録したのに"car"のノードにis_endを立て忘れると、search("car")がFalseを返してしまいます。ノードが「途中で通過しただけ」なのか「単語として登録済み」なのかは、経路の存在とは別に管理する必要があります
starts_withとsearchを混同する: 「接頭辞として存在するか」と「単語そのものとして登録されているか」は別の質問です。前者は経路の有無だけで判定でき、後者は経路の終端でis_endを確認する必要があります
削除で共有ノードを壊す: "car"と"card"が共存するとき、"card"を削除するつもりでdのノードだけでなく共有部分のc -> a -> rまで消してしまうと、"car"も一緒に失われます。削除は「他の単語から参照されていないノードだけ」を末端からたどって取り除く必要があります
固定長配列で無駄なメモリを確保する: 想定するアルファベットが大きい（Unicode全体など）のに固定長配列で子を持つと、ほとんど使われない配列要素にメモリを浪費します。文字種が広い・疎な場合はdictベースの実装が無難です
「トライだから速い」と過信する: 完全一致検索だけが目的なら、ハッシュテーブルとの実効速度差は前述の通りそこまで大きくありません。トライの優位性が効くのは接頭辞に関する操作であることを忘れずに、要件に接頭辞検索や辞書式順序の列挙が本当に必要かを確認してから採用してください
再帰によるDFSでスタックが溢れる: words_with_prefixのような列挙処理を再帰で書くと、非常に長い文字列や深いトライではPythonの再帰上限に達することがあります。大規模データを扱う場合はループ（明示的なスタック）による実装を検討してください

まとめ

トライ木（Trie / prefix tree）は、文字列を1文字ずつ木の枝にほどいて共有し、完全一致検索・接頭辞検索・接頭辞に一致する単語の列挙をまとめて高速に扱うデータ構造。初出はFredkin（1960年）で、先行研究にThue（1912年）とde la Briandais（1959年）がある
構造はノード＋子への枝＋終端フラグの3点セット。子は固定長配列かdictのどちらかで持つのが一般的
挿入・検索・接頭辞検索はいずれも探索文字列の長さLに比例するO(L)。ハッシュテーブルの平均O(1)はハッシュ計算自体のO(L)を含んでおらず、完全一致検索だけなら実効コストはさほど変わらない。トライの真価は接頭辞に関する操作にある
空間計算量は接頭辞の共有度に強く依存するトレードオフ。固定長配列はO(σ)（アルファベットサイズ）ぶんの器を常に確保し、dict実装は使った分だけ使う代わりに定数倍のオーバーヘッドがある
応用は幅広く、オートコンプリート、T9・予測変換、IPルーティングの最長prefix一致（Linuxカーネルのfib_trieがLC-trie/LPC-trieを採用）、スペルチェッカー、辞書式順序での列挙など
発展形として、単独の子しか持たないノードの連鎖をまとめる圧縮トライ（radix tree / PATRICIA trie）があり、複数パターンの同時検索にはAho-Corasickアルゴリズムがトライにサフィックスリンクを加える形で使われる
Python / Java / Go / JavaScript / Rust / C++ いずれも標準ライブラリにはなく、pygtrie・marisa-trie・Apache Commons CollectionsのPatriciaTrie・各言語のクレードやnpmパッケージ、あるいは自作で対応する

まずはTrieNodeとdictだけの素朴な実装を書き、"car" "card" "care"のような接頭辞が重なる単語をいくつか登録して、木がどこで枝分かれするかを手でトレースしてみてください。共有ノードがどこで生まれ、終端フラグがどのノードに立つかを一度目で追うと、圧縮トライやAho-Corasickといった発展形の理解も一気に楽になります。

トライ木（Trie）入門 - 接頭辞検索とオートコンプリートを支えるデータ構造

トライが解く問題 — 接頭辞検索とオートコンプリート

トライの構造 — ノード、子への枝、終端フラグ

素朴な実装 — 挿入・検索・接頭辞検索を動くコードで

計算量 — 文字列長 L に比例する O(L) とハッシュテーブルとの違い

空間計算量のトレードオフ

応用1: オートコンプリート・入力補完

応用2: T9・予測変換

応用3: IPルーティングの最長prefix一致

応用4: スペルチェッカーと辞書式順序での列挙

発展1: 圧縮トライ（radix tree / PATRICIA trie）

発展2: Aho-Corasickアルゴリズムとの関係

各言語の標準ライブラリ状況

よくある落とし穴

まとめ

参考リンク

LRUキャッシュ入門 - ハッシュマップ+双方向連結リストでget/putをO(1)にする仕組み

Union-Find（素集合データ構造）入門 - 経路圧縮とunion by sizeで連結性を高速に管理する

ヒープと優先度付きキュー入門 - O(log n)で最小・最大を取り出すデータ構造

トライが解く問題 — 接頭辞検索とオートコンプリート

トライの構造 — ノード、子への枝、終端フラグ

素朴な実装 — 挿入・検索・接頭辞検索を動くコードで

計算量 — 文字列長 L に比例する O(L) とハッシュテーブルとの違い

空間計算量のトレードオフ

応用1: オートコンプリート・入力補完

応用2: T9・予測変換

応用3: IPルーティングの最長prefix一致

応用4: スペルチェッカーと辞書式順序での列挙

発展1: 圧縮トライ（radix tree / PATRICIA trie）

発展2: Aho-Corasickアルゴリズムとの関係

各言語の標準ライブラリ状況

よくある落とし穴

まとめ

参考リンク

関連記事

LRUキャッシュ入門 - ハッシュマップ+双方向連結リストでget/putをO(1)にする仕組み

Union-Find（素集合データ構造）入門 - 経路圧縮とunion by sizeで連結性を高速に管理する

ヒープと優先度付きキュー入門 - O(log n)で最小・最大を取り出すデータ構造