基数木

基数木（英: Radix tree）またはパトリシア木（英: Patricia tree）とは、文字列集合を格納するトライ木に基づく特殊化された集合データ構造である。パトリシアトライ（英: Patricia trie）とも。通常のトライ木に比較すると、基数木の辺は単一の文字ではなく文字の並びでラベル付けされる。それは、文字列でもよいし、整数やIPアドレスなどを表すビット列でもよい。辞書式順序を適用できるオブジェクトの並びなら何でもラベルとして使用できる。基数木と言った場合、整数を格納する木構造のみを指すことが多く、パトリシア木といった場合は特に格納するデータを限定しないが、基本的に構造や動作原理は同じである。