探索木
三分探索木はトライ木の一種であり、左ノード・中央ノード・右ノードの3個の子ノードを持つことができる探索木である。各ノードは1文字を格納し、二分探索木と同じような順序でデータを格納する。ただし、三分探索木は3つ目のノードを持つことができる。
三分探索木の検索には、全てのパスに検索したい文字列が含まれているかを検査する。
平衡三分探索木の検索時間はO(log n)である。