RBST Query

個人的メモ

2 つの二分木を merge する際にそれぞれの木のサイズに比例した確率で片方の木の根をもう一方の木の根につけるかを決める.
こういう単純だけどうまくいく系はしっかりと解析することが大事なので考えてみるとよい気がする(参考).
サイズ $l$ の Treap とサイズ $r$ の Treap の merge を考えてみるとサイズ $l$ の方の Treap の根が新しくできる Treap の根になる確率は各頂点の優先度が $[0, 1]$ の一様分布に従うと仮定した場合 $l / (r + l)$ となることがわかる. つまり RBST の merge 操作のそれと一致するので, 直感的には RBST も高さの期待値は $\O (\log n)$ になりそうな気がする. むしろ merge 操作を繰り返してできる木の高さの concentration は RBST の方が Treap よりも sharp になるような気がする(？)ので木が大きく平衡から外れるケースはめったになさそう(怪)
個人的には最初木のサイズの大きいほうを常に根にした方がいいんじゃないのかとか思ったがよく考えると最悪の場合左右の子の間での偏りがひどいことになるのでダメだね(ヒープのように左右を自由に swap できるなら Skew Heap や Randomized Heap などのように簡単に高さを $\log$ にすることができる).

(追記)
この記事 にあるように RBST のコピーは木が偏ってしまう可能性が高くなり適していない. 例えば偏った木と偏った木を merge させてできた木はさらに偏りが大きくなる可能性が高そうで, 記事のように自分と自分を merge させるというような操作を繰り返したときに自分がもし偏った木になった場合には自浄作用が働かず, 平衡状態に戻る確率は低くなると予想される.