トライ木（基数木）とは？
トライ木（基数木）とは、文字列を1文字ずつ枝に対応させ、根からの経路そのものがキーを表す木。探索時間がキーの長さだけに依存し、格納件数nに依存しない点が特徴で、共通の接頭辞を1本の経路として共有するため前方一致検索を効率よく行える。
とらいぎ
トライ木（基数木）の意味
文字列を1文字ずつ枝に対応させ、根からの経路そのものがキーを表す木。探索時間がキーの長さだけに依存し、格納件数nに依存しない点が特徴で、共通の接頭辞を1本の経路として共有するため前方一致検索を効率よく行える。
トライ木（基数木）の具体例
検索窓の入力補完で「かい」まで打った時点で「かいしゃ」「かいはつ」を候補に出す処理は、トライ木の該当節点から下の部分木を列挙するだけで済む。IPルーティング表の最長一致検索にも同種の基数木が使われる。
トライ木（基数木）は試験でどう引っ掛けられる？
ハッシュ表は完全一致がO(1)で速いが、前方一致や辞書順の列挙はできない。トライ木はその逆で、用途による使い分けが問われる。また節点ごとに文字種分の配列を持つ素朴な実装はメモリを大量に消費する。
トライ木（基数木）と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。