三分探索木

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

三分探索木(さんぶんたんさくぎ)はトライ木の各ノードを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 + log2nである。比較が文字列ではなく文字である点に注意されたい。

トライ木おける基数木と同様なやり方で、余計なノードをまとめて三分探索木を圧縮することも可能である。たとえば上記の例では、 "cu", "te", "he" および "us" は一つのノードに圧縮できる。

関連項目[編集]

参考文献[編集]

外部リンク[編集]