Splay Tree で三分探索木を組む

はじめに

　最近競技プログラマーの間で Splay Tree のブームが来ているらしいので、それに乗っかり記事を書くことにしました。 Splay Tree は直近にアクセスした値への再アクセスが高速であったり、自己組織化する動的木にも使用されていたりと大変興味深い平衡二分探索木です。本記事では三分探索木を Splay Tree を用いて実装します。
　以下、与えられるキーの文字の種類を σ、文字列長を M、要素数を N とし、各文字は定数時間で大小比較が可能とします。

三分探索木とは

　Trie において、次の文字を二分探索木で管理したものです。これにより各ノードは二分探索木の左子/右子と Trie としての次の文字を指す子を持つことになり、三分探索木と呼ばれる所以となっています。
　クエリの時間計算量はどうなるでしょうか？各二分木を平衡二分木のように平衡させれば、O(Mlog(min(σ, N))) は達成できそうです。なんと三分探索木は、全体での形を考えて平衡させることで O(M+logN) の時間計算量を達成することが出来ます。これは文字列をキーとする平衡二分探索木の O(MlogN) よりもよい計算量です。また Trie や HashMap は O(M) での検索を可能にしますが、あるキーが何番目に大きいか等の順序を用いたクエリを効率的に処理することは出来ません。

	三分探索木と比較して優れている点	三分探索木と比較して劣っている点
Trie	検索が O(M)	順序を用いたクエリが O(Mσ) 遷移に hasmap を使うと最悪時間を保証できない遷移に配列を使うと空間計算量 O(NMσ)
平衡二分探索木	実装が平易	検索が O(MlogN)
HashMap	検索が O(M)	最悪計算量は保証されない順序を持たない

平衡するアルゴリズム

　三分探索木を前述の計算量を達成するように平衡する手法は、二分探索木の平衡に比べて明らかではありません。 Weight Balanced Tree や Treap 等と類似したアルゴリズムが提案されていますが、本記事では Splay Tree と同様の手法によって平衡させます。この手法の利点は余分な情報を持たなくて良いことと、アルゴリズムがとても単純であることです。
　具体的には、Splay Tree と同様に発見したノードを二分木内で Splay します。根になったら、１つ前の文字に移動し、全体での根になるまで Splay を繰り返します。何故この方法によって O(M+logN) が達成されるのでしょうか？ Splay 操作における各回転の償却計算量は、根の手前での単回転以外はそのノードの部分木の大きさの対数の変化で抑えられていたことを思い出しましょう。これは三分探索木を三分木と見たときの部分木の大きさで同様なポテンシャル関数を定義しても成立します。問題となるのは各文字で単回転と手前の文字に移る操作が必要になることですが、これは全体で O(M) なのでそちらに分配すれば Splay 自体の償却計算量の解析とは無関係になります。よって結果として、O(M+logN) の時間計算量が達成されることになります。