トライ木（接頭辞木）
意味・解説
文字列の検索に特化したツリー構造（木構造）の一種。各ノードが文字を表し、ルートからの経路が共通する接頭辞（プレフィックス）を共有する構造。
文字列の集合を保持する際、共通する最初の数文字を一つのパスにまとめることで、メモリ効率を高めつつ、文字列の長さ分のステップで高速に検索ができる。
くわしく
「言葉の『しりとり』をツリーにしたもの」です。
1.仕組み：
例えば「apple」と「apply」を登録する場合、「appl」までのノードを共有し、最後の「e」と「y」で枝分かれさせます。
2.利点：
ハッシュ法と違い、前方一致検索（例：『ap』で始まる言葉をすべて探す）が極めて高速です。ポイントは、スマホの入力予測（オートコンプリート）やIPアドレスのルーティングテーブルの検索など、瞬時の文字列照合が求められるインフラ技術の核心だからです。
例文
検索エンジンのサジェスト機能を実装するため、数百万のキーワードを効率的に管理できるトライ木構造を採用した。
同義語: プレフィックスツリー / 接頭辞木
分類: 文字列探索アルゴリズム