Left-Leaning Red-Black Tree

以下の記事でも書いたが、もう少しだけ補足。

ARC 030: D - グラフではない (Left-Leaning Red-Black Tree) - pekempeyのブログ

join

次の 2 つの木を join するには？

左の木の方が黒高さが高いので、左の木を右に降りていく。右の木と黒高さが同じ頂点が見つかったら、赤頂点を新たに作って繋ぐ。これは黒高さ条件を壊さない。

赤頂点を挟んだ結果、赤頂点が隣接してしまうかもしれない。これを再帰的に修正していく。ここから先は insert/erase ベースの LLRB 木と同じ処理になる。

Algorithms with Python / 赤黒木 (red-black tree)

insert/erase のときと違い、葉ノードにデータを持たせる。内部ノードはデータを繋いでいるだけ。RBSTだと内部にデータを持たせることがあるが、こっちはセグメント木的な持ち方をしている、とも言える。

split

split の擬似コードは次の通り。

pair<node *, node *> split(node *x, int k) {
    if (k == 0) return make_pair(nullptr, x);
    if (k == x->sz) return make_pair(x, nullptr);
    x = push(x);
    if (k < x->l->sz) {
        auto p = split(x->l, k);
        return make_pair(p.first, join(p.second, x->r));
    } else {
        auto p = split(x->r, k - x->l->sz);
        return make_pair(join(x->l, p.first), p.second);
    }
}

RBST を書いたことがあれば、大体同じ処理だと分かる。ひとつ違うのが、単なるポインタの張替えでなく join で繋いでいるということ。 赤黒木条件を保持するにはこうしなければならない。

何度も join が呼び出されるので計算量が危険に見える。そこまできちんと証明していないので怪しいが、join はそもそも O(|x.rank - y.rank|) であり、根に上がるにつれて rank は単調増加であるから合計で O(log n) になる、ということだろう。

実装

以下を参考に。

ARC 030: D - グラフではない (Left-Leaning Red-Black Tree) - pekempeyのブログ

おまけ

1000 頂点くらいでビジュアライズしてみた。定義的には右側の方が低くなりそうだし、left-leaning という名前がついてるくらいなので、左に偏るかなと思った。 1000 頂点だと分かりづらいが、まあよく見れば偏ってる。本当に偏るかは知らない。