Trie木 (トライ木 / Prefix Tree)

文字列の集合を効率的に保存・検索するための木構造です。共通の接頭辞（Prefix）を持つ単語は、木のルートから同じパスを共有します。

例えば “cat” と “car” は、root -> c -> a までは同じノードを辿り、その後に t と r に分岐します。

 計算量:挿入・検索ともに O(L) (Lは単語の長さ)

データ量が増えても、単語の長さのみに依存するため非常に高速です。