トライ木（）やプレフィックス木（）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語には整数の値が対応している。トライ木は一種の決定性有限オートマトンと見ることもできるが、エッジ（枝）に対応する記号（文字）はその順序が暗黙のうちに決定される（辞書順など）。キーは必ずしもノードに格納される必要はない。右図はトライ木の概念を示したもので実装は一般に異なる。トライ木のキーは必ずしも文字列である必要はない。トライ木のアルゴリズムを文字列以外の任意のデータ構造に適用することは容易である。trie という名称は "retrieval"（探索、検索）が語源であるため、"tree" と同じ発音を用いる（リトゥリーヴァル）。しかし、ツリー構造との混同を避けるために「トライ」という読み方を奨励する人もいる。日本語では、「トライ木」という呼び方がほぼ定着している。以下に2分探索木と比較したトライ木の主な利点を挙げる:また、トライ木の欠点は次の通り:トライ木は基本的にキーとして文字列を必要とするが、様々なデータ型を文字列に変換することもできる。例えば、整数を単にビットの列と見れば、文字列と何ら変わらない。ルーティングテーブルやページテーブルではその性質から、プレフィックスが共通の整数がキーとしてよく使われる（つまり偏りがある）。トライ木はキーの長さが可変でキー検索が失敗する場合があるとき（そのキー文字列がキーとされていない場合）、最も便利である。固定長のキーで常に検索が成功するならパトリシア木の方が適している。これは子ノードが1つしかないノードをその子ノードとまとめてしまう方法である（図の例で言えば、"i" のノードと "in" のノードをまとめる）。例えば、経路がほとんど分岐しない構造になっている場合、これはメモリ使用量を削減することになる。トライ木の探索時間は、キー文字列の長さが一定であれば O(1) とみなせるが、より詳細に検討する。キーが "N" 個あるとき、文字の種類が "k" なら、最も長いキーは "logN" 文字がその長さの下限となる。このことから、トライ木の探索時間は厳密には Ω("logN") であり、これは2分探索と同じである。この結果は必ずしもトライ木の利点を否定するものではない。トライ木の高速性の利点は個々の比較が高速である点にある。2分探索では文字列の比較を行い、一回の比較は比較対象の文字列の短いほうを "m" 文字としたとき O("m") が最悪時間となる。一方トライ木では個々の比較は1文字の比較であるため、その時間は一定である。これは単に理論上の違いというわけではない。というのも2分探索木で末端に近いノードまで行くと常にプレフィックスが共通なノードで文字列比較を行うことになり、文字列比較時間が長くなってしまうのである。既に述べたようにトライ木は2分探索木に比較して様々な利点がある。トライ木はハッシュテーブルの代替としても使用でき、次のような利点がある:トライ木をハッシュテーブルとして使用した際の欠点は次の通り:トライ木の典型的な応用として辞書の格納がある。例えば、携帯電話などで使われている。トライ木の利点として検索の高速性と新たなエントリの挿入やエントリの削除の容易性が活用されている。しかし、単に辞書の単語を格納するだけなら（つまり、各単語の意味などが必要とされない場合）、非輪状決定性有限オートマトンのほうがメモリ効率がよい。トライ木はスペルチェッカなどの近似的マッチングアルゴリズムの実装にも適している。以下の擬似コードは与えられた文字列がトライ木にあるかどうかを判定する汎用のアルゴリズムを示したものである。ここで、codice_1 は子ノード群の配列であり、terminal ノードとは格納された単語に対応するノードを意味する。辞書式順序にキー文字列をソートする処理は次のようにトライ木で実現される:これは一種の基数ソートである。トライ木を使って N 個のキーのソートを N 個のプロセッサで行うと（並列アルゴリズム）、その時間は Ω(1) となる。ただし、キーの長さはある一定の上限があるものとする。キーが共通のプレフィックスを持っていたり、同じキーが複数個あったりするので、並列処理の性能上の利点が小さくなるという問題はある。特殊なトライ木としてサフィックス木がある。これを使って高速全文検索のためにテキストのサフィックス（接尾部）でインデックス付けを行うことができる。トライ木を表現する方法は何通りもある。メモリの使用量と操作の速さの間のトレードオフがある。基本的な方法は、ノードに（文字, 子ポインタのリスト）を格納する方法である。これは単純であるが、木の葉の方に近づくと子供の少ないノードがたくさん出来るためメモリの無駄遣いである。別の方法は、ノードに（文字, 子ノードへのポインタ, 兄弟ノードへのポインタ）の3つ組みを格納する方法である。つまり二重連鎖木である。子ノードへのポインタは1つ目の子供だけをさし、2つ目の子供は、その子供から兄弟ノードへのポインタを使い参照する。更に別の方法は、子供の集合を2分探索木で表現する方法である。この場合、トライ木は三分探索木になる。1989年に青江順一がダブル配列を利用する方法を発表した。トライ木は決定性有限オートマトンとして解釈する事が出来るが、決定性有限オートマトンはデフォルト（default）・ベース（base）・次（next）・チェック（check）の4つの配列で表現できる。トライ木の場合はデフォルトは不要である。その上で、s から t へ c により遷移する場合は、以下の関係が成立すれば良い。動的に要素が増えていく場合 next と check は同じように増えていくのでまとめる事が出来るが、base は同じ速度では増えていかず分裂してしまう。そこで、ダブル配列では、base と next を統合し、以下の関係が成立するように管理する。すると、base と check だけが残り、この2つは同じ速さで増えていき、一つの構造体にまとめる事が出来る。ある要素がトライ木に含まれているかどうか調べる際に、二重連鎖木を使った方法では、兄弟ノードはポインタ（連結リスト）をたどって行かないといけないが、ダブル配列では一発で遷移できる。実装としては Theppitak Karoonboonyanan が libdatrie を公開している。二分トライ木（）やビット単位トライ木（）とは、整数を格納するトライ木で、上位ビットから 0 また 1 で左右に分岐する。高速化のためのテクニックとして、下記の２つの方法が使える。x-高速トライ木（）は、検索キーとして与えられた整数以上(以下)の値をもつ、キーに最も近い葉ノードを得る操作(successor, predecessor)を高速にできるようにした二分トライ木のバリエーションである。通常の二分トライ木との相違点は、階層高さごとのハッシュテーブル、葉ノード同士の双方向連結リスト、中間ノードが子ノードを0側(1側)のひとつしか持たない時に格納される、その中間ノード下で最大(最小)値をもつ葉ノードへのリンク(descendant pointer)を持つことである。。階層にたいして二分探索をおこなうことで、木に格納する整数のビット数 w に対し、Successor, Predecessorの時間計算量がO(log w)となる。1982年に Dan E. Willard が発表した。y-高速トライ木（）とは、格納する整数が w ビットの時、x-fast trie に全体の 1/w だけしか格納せず、残りを Treap などの平衡2分探索木に O(w) 個ずつに分けて入れる。これにより全体の空間計算量が、実際に木に格納されたデータの数 n に対し O(n) となり、x-高速トライ木より改善する。また、追加・削除の時間計算量が O(log w) になる。1982年に Dan E. Willard が x-fast trie と同時に発表した。

出典:wikipedia