三分探索木

三分探索木（さんぶんたんさくぎ、英: ternary search tree）は、トライ木の各ノードを二分探索木として表現したデータ構造である。各ノードは文字列中の文字と以下の三つの子ノードを持つ。

• その文字の代わりに、より小さな文字を指す左ノード
• その文字の代わりに、より大きな文字を指す右ノード
• その文字の次の文字を指す中央ノード

他のトライ木構造と同じく、三分探索木の各ノードは格納された文字列の接頭辞に対応している。中央ノードに格納された木は、そこに至るまでのノードを共通接頭辞として持つ。

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

上記の三分探索木は "as", "at", "cup", "cute", "he", "i", "us" が値として格納されている。三分探索木から値を取得するには次のような操作を行う。

1. 頂点ノードから「子に中央ノードを持たないノード」までを辿り、その経路を保存する
   1. "c-a-t-s"
   2. "c-a-t"
   3. "c-u-t-p"
   4. "c-u-t-e"
   5. "c-h-e"
   6. "c-h-u-i"
   7. "c-h-u-s"
2. それらの経路に対して頂点から順に、子が中央ノードでなければ自身の文字を消す
   1. "a-s"
      1. "c-a-t-s" の "c" に対して "a" は左ノードで繋がっているので "c" を消す
      2. "a-t-s" の "a" に対して "t" は中央ノードで繋がっているので "a" を残す
      3. "a-t-s" の "t" に対して "s" は左ノードで繋がっているので "t" を消す
      4. "a-s" の "s" は終端ノードなので残す
   2. "a-t"
   3. "c-u-p"
   4. "c-u-t-e"
   5. "h-e"
   6. "i"
   7. "u-s"

このようにして、三分探索木から値を取得できる。

なお、値として "cute" と "cut" を含む（他の値の部分文字列であるような値を含む）ような三分探索木は、終端文字を表すノードを用いることで表現できる。上記の例に値 "cut" を追加した場合の例を以下に示す（ここでは終端文字を # と表している）。

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

二分探索木と同様、三分探索木を平衡させることも可能である。長さmの文字列を、要素nを格納した平衡三分探索木から探索するのに必要な文字比較はたかだかm + log₂nである。比較が文字列ではなく文字である点に注意されたい。

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

関連項目

• 二分探索木
• ハッシュテーブル

参考文献

• 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