トライ木 とは？

できるよ。ハッシュマップはキーの完全一致検索によく使う。トライ木は共通の接頭辞を木の経路として共有するので、「ca」で始まる単語を探すような前方一致にも使いやすいんだ。どの方法がよいかは、必要な検索に合わせて考えよう。

たとえば「cat」「car」「card」を格納する。ルートからc→aまでを共有して、tとrへ分岐するよ。rの下にはdもある。「car」ならc→a→rとたどり、その場所に単語の終端が記録されていれば、登録済みとわかるんだ。

終端をノードに記録する方式なら、葉以外にも置けるよ。「car」のrには「card」のdという子があるけれど、rも単語の終端だ。一方、c→aまでたどれても「ca」が登録済みとは限らない。経路があることと、単語として登録されていることを区別するんだ。

接頭辞の場所を見つけた後、その下をたどって登録された単語を集める必要があるよ。候補の数や文字数が多ければ、その分の時間もかかる。長さMのキーをO(M)で探せるのは、各文字に対応する子を定数時間で選べる実装での話なんだ。

子への参照を文字種の数だけ配列で持つ実装では、使わない欄も場所を取るよ。子がある文字だけをMapなどに記録する方法や、枝分かれのない経路をまとめる圧縮トライもある。メモリ量と探索の速さは、文字種、データ、実装の選び方に左右されるんだ。 辞書や入力候補の検索、IP経路の最長一致などにも使われるよ。