トライ (データ構造)
2分探索木と比較したトライ木の主な利点:
キー検索が高速である。長さ m のキー検索の時間計算量は最悪でも O(m) である。2分探索木での時間計算量は O(log n) である。ただしn は木を構成するノード数である(木の深さに応じた時間がかかり、2分探索木の深さは n の対数となる)。トライ木が検索処理で行う文字でインデックス付けした配列の操作なども、実際のマシンでは高速である。
多数の短い文字列を格納する場合にはトライ木の方がメモリを節約できる。これはキーが明示的に格納されないためであり、複数のキーがノードを共有するためである。
トライ木は最も長いプレフィックスとマッチするよう探索を進められるので、最も長いプレフィックスが共通なキーを効率的に捜せる。また、そのような共通プレフィックスに対応したノードに新たな値を格納できる。
トライ木は木構造として平衡を保つ必要はない。2分探索木は深さが平衡していないと性能に悪影響がある(平衡2分探索木参照)。
トライ木の欠点:
トライ木はキーの順序を与えるが、辞書順でなければならない。
トライ木は入力ノード数に対して深さが極めて大きくなりうる。