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