全順序集合の列の集合 \{s_0, s_1, \dots s_{n - 1}\} を扱う.

空間計算量\Theta(\sum |s_i|)

\mathtt{new}()

空の状態でデータ構造を作成する

時間計算量\Theta(1)

\mathtt{find}(x)

xを検索する

存在の判定や, 紐付いたデータの取得など

時間計算量\Theta(|x|+\log n)

\mathtt{insert}(x)

xを集合に追加する

時間計算量\Theta(|x|+\log n)

\mathtt{remove}(x)

xを集合から削除する

時間計算量\Theta(|x|+\log n)

Trie の次の文字へのリンクを二分探索木で表現する.

各ノードは二分探索木としての子と Trie としての子を持ち,三分木を成す.

二分探索木と同様に平衡させるアルゴリズムが存在し,操作の時間計算量が\Theta(|x|+\log n)に改善される.

\{(A,B),(A,E,G),(A,F),(C),(D,A),(D,B)\} を管理する Ternary Search Tree.

平衡二分探索木と同様に,key の index などを管理することが出来る.