トライ木 とは？

完全一致検索ならハッシュマップでO(1)で十分。でもトライ木が輝くのは「前方一致検索」だよ。「pro」で始まる単語を全部取得したい場合、ハッシュマップは全エントリを走査するO(n)が必要。トライ木なら「pro」のノードまで辿って、そこから下のすべてのノードを返すだけ。オートコンプリートに最適なんだよ

例えば「cat」「car」「card」を格納すると、ルートから「c」→「a」→「t」（catの終端）と「r」（carの終端）→「d」（cardの終端）という木になる。「ca」の共通部分を共有して、分岐するところだけ枝分かれする。「car」を検索するなら、c→a→rとたどって終端マークがあれば存在するとわかるんだよ

各ノードが子ノードへのポインタを文字種分（アルファベットなら26個、Unicode全体なら膨大）持つから、密度が低いとスカスカになる。対策として、①圧縮トライ（Patricia Trie）で共通前方部分をまとめる、②Map/HashMapで子ノードを管理、③ダブル配列トライ（日本語形態素解析で使われる高速実装）がある

①検索エンジンのオートコンプリート、②スマートフォンの予測変換、③IPアドレスのルーティングテーブル（Longest Prefix Match）、④スペルチェッカー。日本語の形態素解析器（MeCab等）はダブル配列トライを使っている。DNSサーバーのドメイン検索もトライ木ベースの実装が多いんだよ