接尾辞木
各ノードが最初の子ノードへのポインタを持ち、子ノード同士を線形リストでつなぐ(子供同士のリストなので兄弟リスト)。ハッシュテーブル、ソート済み/未ソート配列(動的配列)、平衡2分探索木なども使われ、それぞれ実行時間特性が異なる。ここでは以下に注目する。
ある文字に対応する子ノードを探すコスト
子ノードを挿入するコスト
あるノードの全子ノードをリストアップするコスト(下表では子ノード数で割った値)
文字のサイズ(種類)を σ {\displaystyle \sigma } としたとき、コストは以下のようになる。
なお、挿入コストは償却計算量(amortized complexity)であり、ハッシュ操作のコストは衝突が発生しない完全ハッシュを前提としている。
各ノードや枝に情報が分散するため、接尾辞木は効率が悪く、よい実装であっても元の文字列の約10倍から20倍のメモリを消費する。接尾辞配列はこれを4倍程度に削減でき、研究者はさらなるメモリ使用量削減方法を模索している。
各ノードまたは枝に要するメモリ空間を Θ ( 1 ) {\displaystyle \Theta (1)} で表すと、接尾辞木全体には Θ ( n ) {\displaystyle \Theta (n)} の空間が必要である。枝の長さ(対応する文字数)の総和は O ( n 2 ) {\displaystyle O(n^{2})} だが、各枝に対応する情報は S の部分文字列の位置と長さであり(部分文字列のコピーを枝ごとに持つ必要はない)、全体として必要なメモリ空間は Θ ( n ) {\displaystyle \Theta (n)} ワードとなる。最悪の場合の例として、フィボナッチ列を接尾辞木で表すと、 2 n {\displaystyle 2n} 個のノードを要する。
接尾辞木を実装する際の重要な問題として、親ノードと子ノードの関係の表し方がある。最も典型的な実装は「兄弟リスト; sibling list」と呼ばれる線形リストを使う方法である。