トライ (データ構造)
トライ木を表現する方法は何通りもある。メモリの使用量と操作の速さの間のトレードオフがある。
基本的な方法は、ノードに(文字, 子ポインタのリスト)を格納する方法である。これは単純であるが、木の葉の方に近づくと子供の少ないノードがたくさん出来るためメモリの無駄遣いである。
既に述べたようにトライ木は2分探索木に比較して様々な利点がある。トライ木はハッシュテーブルの代替としても使用でき、次のような利点がある:
理論上、平均検索性能は同じだが、実測するとトライ木の方が速い。
ハッシュテーブルの検索の最悪時間は O(N) である。
キーの衝突(コリジョン)が発生しない。
ハッシュ関数を用意する必要がない。
トライ木ではキーの辞書順を自動的に生成できる。
トライ木をハッシュテーブルの代替として使用した際の欠点は次の通り:
格納されている全キーを文字列として取り出すのが簡単ではない。
ハッシュテーブルよりもメモリ効率が悪い。
ハッシュテーブルはプログラミング言語に最初から用意されているが、トライ木はそうではない。