三分探索木

三分探索木（さんぶんたんさくぎ、）は、トライ木の各ノードを二分探索木として表現したデータ構造である。各ノードは文字列中の文字と以下の三つの子ノードを持つ。
他のトライ木構造と同じく、三分探索木の各ノードは格納された文字列の接頭辞に対応している。中央ノードに格納された木は、そこに至るまでのノードを共通接頭辞として持つ。
上記の三分探索木は "as", "at", "cup", "cute", "he", "i", "us" が値として格納されている。三分探索木から値を取得するには次のような操作を行う。
このようにして、三分探索木から値を取得できる。
なお、値として "cute" と "cut" を含む（他の値の部分文字列であるような値を含む）ような三分探索木は、終端文字を表すノードを用いることで表現できる。上記の例に値 "cut" を追加した場合の例を以下に示す（ここでは終端文字を # と表している）。
二分探索木と同様、三分探索木を平衡させることも可能である。長さ"m"の文字列を、要素"n"を格納した平衡三分探索木から探索するのに必要な文字比較はたかだか"m" + log2"n"である。比較が文字列ではなく文字である点に注意されたい。
トライ木おける基数木と同様なやり方で、余計なノードをまとめて三分探索木を圧縮することも可能である。例えば上記の最初の例では、 "cu", "te", "he" および "us" は一つのノードに圧縮できる。