三分探索木
それらの経路に対して頂点から順に、子が中央ノードでなければ自身の文字を消す "a-s" "c-a-t-s" の "c" に対して "a" は左ノードで繋がっているので "c" を消す "a-t-s" の "a" に対して "t" は中央ノードで繋がっているので "a" を残す "a-t-s" の "t" に対して "s" は左ノードで繋がっているので "t" を消す "a-s" の "s" は終端ノードなので残す "a-t" "c-u-p" "c-u-t-e" "h-e" "i" "u-s"
このようにして、三分探索木から値を取得できる。
なお、値として "cute" と "cut" を含む(他の値の部分文字列であるような値を含む)ような三分探索木は、終端文字を表すノードを用いることで表現できる。上記の例に値 "cut" を追加した場合の例を以下に示す(ここでは終端文字を # と表している)。
二分探索木と同様、三分探索木を平衡させることも可能である。長さmの文字列を、要素nを格納した平衡三分探索木から探索するのに必要な文字比較はたかだかm + log2nである。比較が文字列ではなく文字である点に注意されたい。
トライ木おける基数木と同様なやり方で、余計なノードをまとめて三分探索木を圧縮することも可能である。例えば上記の最初の例では、 "cu", "te", "he" および "us" は一つのノードに圧縮できる。