トライ (データ構造)
特殊なトライ木としてサフィックス木がある。これを使って高速全文検索のためにテキストのサフィックス(接尾部)でインデックス付けを行うことができる。
例えば、少数の非常に長い文字列を格納するトライ木などである(この場合、パトリシア木が適する)。
トライ木のアルゴリズムは単純な2分探索木よりも複雑である。
データを文字列として表すのは常に簡単とは言えない。例えば、複雑なデータ構造や浮動小数点数などをキーとする場合、工夫が必要となる。
トライ木は基本的にキーとして文字列を必要とするが、様々なデータ型を文字列に変換することもできる。例えば、整数を単にビットの列と見れば、文字列と何ら変わらない。ルーティングテーブルやページテーブルではその性質から、プレフィックスが共通の整数がキーとしてよく使われる(つまり偏りがある)。
トライ木はキーの長さが可変でキー検索が失敗する場合があるとき(そのキー文字列がキーとされていない場合)、最も便利である。固定長のキーで常に検索が成功するならパトリシア木の方が適している。これは子ノードが1つしかないノードをその子ノードとまとめてしまう方法である(図の例で言えば、"i" のノードと "in" のノードをまとめる)。例えば、経路がほとんど分岐しない構造になっている場合、これはメモリ使用量を削減することになる。