RBST(Randomize Binary Search Tree)の計算量について考えてみた

RBSTは万能かつ簡潔な平衡二分木として有名ですね

Q.でもこれって計算量どうなんやろ
A.なんかいい感じやねん

のままだとよくないかなぁと思ってちょっと考えてみました

注意点として今回の記事では全部i番目というのは0-indexedです
あと、スピリチュアルです

"RBST木"を以下の感じで定義します

• 根がi番目の可能性はそれぞれ1/(木のサイズ)
• 左右の子はそれぞれRBST木

例えばサイズ7のRBST木の根を考えると
0と1と2と3と4と5と6がそれぞれ透明度1/7で重ね合わさってる感じ

そのなかで根が4の木をとりだして、根の左の子の根を見てみると0と1と2と3が透明度1/28で重ね合わさってる

Q.RBST木の高さの平均値的なのはO(logN)なの？
A.問題 J : 乱択平衡分二分探索木

まあこれはTreapだけど多少はね？(僕はこの問題を解いていません)

RBST木の高さの平均値的なのがO(logN)ならば、RBST木をmerge/splitした時にRBST木になることが示せればいい感じになるはず

merge

Node* merge(Node* l, Node* r) {
    if (!l->sz) return r;
    if (!r->sz) return l;
    if (xor128() % (l->sz + r->sz) < l->sz) {
        l->r = merge(l->r, r);
        return l->update();
    } else {
        r->l = merge(l, r->l);
        return r->update();
    }
}

この関数について、"lとrがRBST木なら, 返り値もRBST木である"ことを示せばいい。

xor128() % (l->sz + r->sz) < l->sz と、lとrがRBST木であることから、返り値の根は全部等確率

ここで、l->r = merge(l->r, r)に注目するとl->rとrは当然両方RBST木だから返り値もRBST木

l->lもRBST木だから結局lはRBST木

逆も然り

split

pair<Node*, Node*> split(Node* x, int k) {
    assert(0 <= k && k <= x->sz);
    if (!x->sz) return {last, last};
    if (k <= x->l->sz) {
        auto y = split(x->l, k);
        x->l = y.second;
        y.second = x->update();
        return y;
    } else {
        auto y = split(x->r, k- x->l->sz -1);
        x->r = y.first;
        y.first = x->update();
        return y;
    }
}

これについて、"xがRBST木なら返り値は両方RBST木"ということを示す ただしk

if (!x->sz) return {last, last}はどうでもいい

if (k <= x->l->sz) が真になった場合

auto y = split(x->l, k) だが, x->lがRBST木ゆえyは両方RBST木
よって返り値の左側は当然RBST木

右側の根は, xがRBST木ゆえk番目~(xのサイズ-1)番目で等確率
ゆえ右側もRBST木

偽になった場合->同様

ところで

RBSTのTってTreeだからRBST木ってヤバい