|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 三 ： [み] 1. (num) three ・ 三分 ： [さんぶん, さんぷん] (n) three minutes ・ 分 ： [ぶん, ふん] 1. (n,n-suf,pref) (1) part 2. segment 3. share 4. ration 5. (2) rate 6. (3) degree 7. one's lot 8. one's status 9. relation 10. duty 1 1. kind 12. lot 13. (4) in proportion to 14. just as much as 1 ・ 探索 ： [たんさく] 1. (n,vs) search 2. hunt 3. (item of) research 4. exploration 5. investigation ・ 探索木 ： [たんさくぎ] (n) search tree ・ 索 ： [さく] 【名詞】 1. rope 2. cord ・ 木 ： [き] 【名詞】 1. tree 2. wood 3. timber
三分探索木（さんぶんたんさくぎ、）は、トライ木の各ノードを2分探索木として表現したデータ構造である。各ノードは文字列中の文字と、以下の三つの子ノードを持つ。 * その文字より小さな文字に対応する文字列を格納する左ノード * その文字より大きな文字に対応する文字列を格納する右ノード * その文字と一致する文字列を格納する中央ノード 以下は "as", "at", "cup", "cute", "he", "i" および "us" が格納された三分探索木である。
他のトライ木構造と同じく、三分探索木の各ノードは格納された文字列の接頭辞に対応している。中央ノードに格納された木は、そこに至るまでのノードを共通接頭辞として持つ。 2分探索木と同様、三分探索木を平衡させることも可能である。長さ''m''の文字列を、要素''n''を格納した平衡三分探索木から探索するのに必要な文字比較はたかだか''m'' + log2''n''である。比較が文字列ではなく文字である点に注意されたい。 トライ木おける基数木と同様なやり方で、余計なノードをまとめて三分探索木を圧縮することも可能である。たとえば上記の例では、 "cu", "te", "he" および "us" は一つのノードに圧縮できる。 == 関連項目 == *2分探索木 *ハッシュテーブル 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「三分探索木」の詳細全文を読む スポンサード リンク
|