|
right 基数木（英: Radix tree）またはパトリシア木（英: Patricia tree）とは、文字列集合を格納するトライ木に基づく特殊化された集合データ構造である。パトリシアトライ（英: Patricia trie）とも。通常のトライ木に比較すると、基数木の辺は単一の文字ではなく文字の並びでラベル付けされる。それは、文字列でもよいし、整数やIPアドレスなどを表すビット列でもよい。辞書式順序を適用できるオブジェクトの並びなら何でもラベルとして使用できる。基数木と言った場合、整数を格納する木構造のみを指すことが多く、パトリシア木といった場合は特に格納するデータを限定しないが、基本的に構造や動作原理は同じである。 == 概要 == 基数木は簡単に言えばメモリ使用量を最適化したトライ木であり、トライ木で子ノードが1つしかないノードを子ノードとマージしたものである。その結果、内部ノードは必ず2つ以上の子ノードを持つことになる。通常のトライ木と異なり、辺には1つの文字だけでなく文字の並びがラベルとして付与される。これは、集合が小さい場合（特に長い文字列の集合）や長い接頭部を共有する文字列の集合などで効果を発揮する。 以下のような主な操作がサポートされており、いずれも O(''k'') である（''k'' は集合内の最大文字列長）。 ; 検索 : ある文字列が集合に含まれているかどうかを調べる。この操作はトライ木とほぼ同じだが、辺によっては複数の文字に対応している点が異なる。 ; 挿入 : 木構造に文字列を追加する。文字列が一致するところまで走査していき、そこから新たな辺を追加して残りの文字列をラベルとして付ける。なお、残りの文字列の先頭から一部分までが共通な別の辺がすでにある場合、共通部分を辺として新たに作り、そこから2つに分かれるようにする。 ; 削除 : 文字列を木構造から削除する。まず、対応する葉ノード（と辺）を削除し、その親ノードの別の子ノードが1つしかない場合は、マージを行う。 ; 辞書順の前の項目を探す : 辞書式順序で1つ前の文字列を探す。 ; 辞書順の後の項目を探す : 辞書式順序で1つ後の文字列を探す。 基数木の典型的拡張として、ノードを「白」と「黒」に分ける方式がある。ある文字列が格納されているかを調べるとき、根ノードから文字列とラベルが一致する辺を辿っていく。文字列が全てラベルと一致したとき、その位置にあるノードが「黒」だった場合、検索は失敗となる。ノードが「白」だった場合、検索は成功となる。これを利用すると、接頭部が共通な多数の文字列で木構造を構築して、それらのノードは「白」にしておき、例外を「黒」を使って示すということができる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「基数木」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Radix tree 」があります。 スポンサード リンク
|
