Splay Tree で三分探索木を組む - noshi91のメモはじめに 最近競技プログラマーの間で Splay Tree のブームが来ているらしいので、それに乗っかり記事を書くことにしました。 Splay Tree は直近にアクセスした値への再アクセスが高速であったり、自己組織化する動的木にも使用されていたりと大変興味深い平衡二分探索木です。 本記事では三分探索木を Splay Tree を用いて実装します。 以下、与えられるキーの文字の種類を σ、文字列長を M、要素数を N とし、各文字は定数時間で大小比較が可能とします。 三分探索木とは Trie において、次の文字を二分探索木で管理したものです。 これにより各ノードは二分探索木の左子/右子と Trie としての次の文字を指す子を持つことになり、三分探索木と呼ばれる所以となっています。 クエリの時間計算量はどうなるでしょうか？ 各二分木を平衡二分木のように平衡させれば、O(Mlog(min(σ,
