三分探索木について

Words near each other

・三分の一
・三分の一の法則
・三分の二
・三分一博志
・三分一湧水
・三分一銀納
・三分位数
・三分割法
・三分子反応
・三分山町
・ 三分探索木
・三分損益法
・三分搗
・三列生
・三列風切
・三列風切羽
・三別抄
・三刺激値
・三刻志
・三剣もとか

Dictionary Lists

mini英和辞書

翻訳と辞書　辞書検索 [ 開発暫定版 ]

スポンサードリンク

三分探索木：ウィキペディア日本語版

三分探索木[さんぶんたんさくぎ]
三分探索木（さんぶんたんさくぎ、）は、トライ木の各ノードを2分探索木として表現したデータ構造である。各ノードは文字列中の文字と、以下の三つの子ノードを持つ。
* その文字より小さな文字に対応する文字列を格納する左ノード
* その文字より大きな文字に対応する文字列を格納する右ノード
* その文字と一致する文字列を格納する中央ノード
以下は "as", "at", "cup", "cute", "he", "i" および "us" が格納された三分探索木である。


           c
         / | \
        a  u  h
        |  |  | \
        t  t  e  u
      /  / |   / |
     s  p  e  i  s

他のトライ木構造と同じく、三分探索木の各ノードは格納された文字列の接頭辞に対応している。中央ノードに格納された木は、そこに至るまでのノードを共通接頭辞として持つ。
2分探索木と同様、三分探索木を平衡させることも可能である。長さ''m''の文字列を、要素''n''を格納した平衡三分探索木から探索するのに必要な文字比較はたかだか''m'' + log₂''n''である。比較が文字列ではなく文字である点に注意されたい。
トライ木おける基数木と同様なやり方で、余計なノードをまとめて三分探索木を圧縮することも可能である。たとえば上記の例では、 "cu", "te", "he" および "us" は一つのノードに圧縮できる。
== 関連項目 ==

*2分探索木
*ハッシュテーブル

抄文引用元・出典: フリー百科事典『ウィキペディア（Wikipedia）』
■ウィキペディアで「三分探索木」の詳細全文を読む

スポンサードリンク

翻訳と辞書 : 翻訳のためのインターネットリソース