三分探索木

三分探索木（さんぶんたんさくぎ）はトライ木の各ノードを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分探索木
• ハッシュテーブル

参考文献

• Ternary Search Trees (Jon Bentley and Bob Sedgewick)

外部リンク

• Ternary Search Trees
• Tree::Ternary (Perl module)
• Ternary Search Tree code
• STL-compliant Ternary Search Tree in C++
• Ternary Search Tree in C++
• Ternary Search Tree in Ruby
• pytst - C++ Ternary Search Tree implementation with Python bindings
• Algorithm for generating search strings given a Ternary Search Tree