三分探索木

二分探索木と同様、三分探索木を平衡させることも可能である。長さmの文字列を、要素nを格納した平衡三分探索木から探索するのに必要な文字比較はたかだかm + log₂nである。比較が文字列ではなく文字である点に注意されたい。トライ木おける基数木と同様なやり方で、余計なノードをまとめて三分探索木を圧縮することも可能である。例えば上記の最初の例では、 \"cu\", \"te\", \"he\" および \"us\" は一つのノードに圧縮できる。