Ternary Search Tree
Operations
全順序集合の列の集合 $ \{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)
Summary
Trie の次の文字へのリンクを二分探索木で表現する.
各ノードは二分探索木としての子と Trie としての子を持ち,三分木を成す.
二分探索木と同様に平衡させるアルゴリズムが存在し,操作の時間計算量が$ \Theta(|x|+\log n)に改善される.
https://gyazo.com/52d0407ff9368e27ed81f4bb2a82302e
$ \{(A,B),(A,E,G),(A,F),(C),(D,A),(D,B)\} を管理する Ternary Search Tree.
References
Notes
平衡二分探索木と同様に,key の index などを管理することが出来る.
Implementations