トライ木が検索処理で行う文字でインデックス付けした配列の操作なども、実際のマシンでは高速である。多数の短い文字列を格納する場合にはトライ木の方がメモリを節約できる。これはキーが明示的に格納されないためであり、複数のキーによってノードが共有されるためである。トライ木は最も長いプレフィックスとマッチするので、あるキーと最も長いプレフィックスが共通なキーを効率的に捜すこともできる。そのような共通プレフィックスに対応したノードに新たに値を格納することもできる。トライ木は木構造として平衡を保つ必要はない。2分探索木は深さが平衡していないと性能に悪影響がある(平衡2分探索木参照)。トライ木の欠点は次の通り:トライ木はキーの順序を与えるが、それは辞書式順序でなければならない。トライ木は状況によっては極めて巨大になる。少数の非常に長い文字列を格納するトライ木などである(この場合はパトリシア木が適している)。トライ木のアルゴリズムは単純な2分探索木よりも複雑である。データを文字列として表すのは常に簡単とは言えない。複雑なデータ構造や浮動小数点数などをキーとする場合、工夫が必要となる。トライ木は基本的にキーとして文字列を必要とするが、様々なデータ型を文字列に変換することもできる。整数を単にビットの列と見れば、文字列と何ら変わらない。ルーティングテーブルやページテーブルではその性質から、プレフィックスが共通の整数がキーとしてよく使われる(つまり偏りがある)。トライ木はキーの長さが可変でキー検索が失敗する場合があるとき(そのキー文字列がキーとされていない場合)、最も便利である。固定長のキーで常に検索が成功するならパトリシア木の方が適している。経路がほとんど分岐しない構造になっている場合、これはメモリ使用量を削減することになる。みなせるが、より詳細に検討する。文字がその長さの下限となる。あり、これは2分探索と同じである。この結果は必ずしもトライ木の利点を否定するものではない。トライ木の高速性の利点は個々の比較が高速である点にある。トライ木では個々の比較は1文字の比較であるため、その時間は一定である。これは単に理論上の違いというわけではない。いうのも2分探索木で末端に近いノードまで行くと常にプレフィックスが共通なノードで文字列比較を行うことになり、文字列比較時間が長くなってしまうのである。応用[編集]他のデータ構造の代替[編集]既に述べたようにトライ木は2分探索木に比較して様々な利点がある。同じだが、実測するとトライ木の方が速い。キーの衝突(コリジョン)が発生しない。ハッシュ関数を用意する必要がない。トライ木ではキーの辞書順を自動的に生成できる。トライ木をハッシュテーブルとして使用した際の欠点は次の通り:格納されている全キーを文字列として取り出すのが簡単ではない。ハッシュテーブルよりもメモリ効率が悪い。ハッシュテーブルはプログラミング言語に最初から用意されているが、トライ木はそうではない。辞書表現[編集]トライ木の典型的な応用として辞書の格納がある。携帯電話などで使われている。トライ木の利点として検索の高速性と新たなエントリの挿入やエントリの削除の容易性が活用されている。オートマトンのほうがメモリ効率がよい。トライ木はスペルチェッカなどの近似的マッチングアルゴリズムの実装にも適している。擬似コード[編集]以下の擬似コードは与えられた文字列がトライ木にあるかどうかを判定する汎用のアルゴリズムを示したものである。ノードとは格納された単語に対応するノードを意味する。}}ソート[編集]辞書式順序にキー文字列をソートする処理は次のようにトライ木で実現される:全キーをトライ木に挿入する。深さ優先探索のような決まった順序でトライ木から全キーを取り出す。これは一種の基数ソートである。キーの長さはある一定の上限があるものとする。キーが共通のプレフィックスを持っていたり、同じキーが複数個あったりするので、並列処理の性能上の利点が小さくなるという問題はある。全文検索[編集]特殊なトライ木としてサフィックス木がある。これを使って高速全文検索のためにテキストのサフィックス(接尾部)でインデックス付けを行うことができる。実装の工夫[編集]トライ木を二重連鎖木で実装した物。縦の矢印は子ポインタを表現し、横の点線の矢印は兄弟ポインタを表現する。リストはアルファベット順で走査出来るようにソートされている。トライ木を表現する方法は何通りもある。メモリの使用量と操作の速さの間のトレードオフがある。子ポインタのリスト)を格納する方法である。これは単純であるが、木の葉の方に近づくと子供の少ないノードがたくさん出来るためメモリの無駄遣いである。兄弟ノードへのポインタ)の3つ組みを格納する方法である。子ノードへのポインタは1つ目の子供だけをさし、2つ目の子供は、その子供から兄弟ノードへのポインタを使い参照する。別の方法は、子供の集合を2分探索木で表現する方法である。この場合、トライ木は三分探索木になる。ダブル配列[編集]1989年に青江順一がダブル配列を利用する方法を発表した[1]。・チェック(check)の4つの配列で表現できる[2][3]。トライ木の場合はデフォルトは不要である。より遷移する場合は、以下の関係が成立すれば良い。同じ速度では増えていかず分裂してしまう。統合し、以下の関係が成立するように管理する。残り、この2つは同じ速さで増えていき、一つの構造体にまとめる事が出来る。ある要素がトライ木に含まれているかどうか調べる際に、二重連鎖木を使った方法では、兄弟ノードはポインタ(連結リスト)をたどって行かないといけないが、ダブル配列では一発で遷移できる。左右に分岐する[5]。高速化のためのテクニックとして、下記の2つの方法が使える。葉ノードは子が無いので、子を指すポインタが空くので、葉ノード同士を双方向連結リストでつないでしまう。jumpポインタをノードに付け、一気に葉ノードまでジャンプする。x-高速トライ木[編集]x高速トライ木の例。(1012)を格納する。pointerを表す。1であることがわかる。predecessor)を高速にできるようにした二分トライ木のバリエーションである。pointer)を持つことである。