トライ木

トライ木とは

トライ木（Trie）とは、順序付き木構造 (データ構造)の一種。プレフィックス木（Prefix Tree）とも呼ばれる。キーが文字列である連想配列の実装構造として使われる。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。

• 出典: フリー百科事典『ウィキペディア（Wikipedia）』
• [ トライ木の改定履歴 ]