永続赤黒木を実装した時のメモ

はじめに

Copy&Paste の解説スライドを読んで，永続赤黒木を実装してみました．

merge-split ベースの赤黒木の実装は insert-erase ベースのものと比較するとかなりシンプルで，1重回転だけで実装できますし，行数的にもRBST+50〜60行で実装できます．

ただし，上のスライドだけだと，なんでこれで動くのかを結構考察する必要があったり，split に関しては擬似コードどおりに書いても正しく動かなかったりするので，備忘録も兼ねてメモしておきます．

実装前に理解しておくべきこと

• P.11 の平衝条件はしっかり頭に叩き込んでおきましょう．
  1. 各ノードには赤か黒の色がついている
  2. 根は黒
  3. 葉は黒
  4. 赤いノードは隣接しない
  5. 根から葉までのパス上の黒いノード数は一定
• さらに，上記の条件から以下のことが導けます
  6. 条件3,5 から，葉以外のノードは必ず2つの子を持つ
     • 持たないとすれば，条件5に反する
     • この性質を覚えておくと，実装上 null チェックの数が少なくて済みます
  7. 変更によって根が赤になった場合，単純に根を黒に戻せば良い．
     • 条件4, 5は保たれるので問題ない
• このアルゴリズムで値を持つのは葉だけ
  • 一般に出回っているRBSTとは違うので注意しましょう．
• 各ノードはランクを持つ（P. 13）
  • 葉から自身までの黒いノードの数．ただし自分自身は含まない．
  • 条件5 から，a.l.rank + is_black(a.l.color) と a.r.rank + is_black(a.r.color) は一致する．
  • したがって，計算時は左右のどちらの子を使って計算してもよい．

ノードの生成

葉と中間ノードの性質が全く異なるので，別々の生成関数を用意しておくと便利です．

function leaf(value)
    a := new Node.
    a.color := 黒.
    a.size := 1.
    a.rank := 0.
    a.value := value.
    a.l := null.
    a.r := null.
    return a.

function node(l, r, color)
    a := new Node.
    a.color := color.
    a.size := l.size + r.size.
    a.rank := l.rank + (1 if l.color = 黒 else 0).
    a.l := l.
    a.r := r.
    return a.

Merge

Merge 操作は P.17〜22 に書かれています．基本的には，P.18, 19 の擬似コードを実装すれば動きます．ただし，（上と同様）の部分は，左右反転して実装する必要があることに注意してください．全部書くと以下のようになります．

function mergeSub(a, b)
    if (a.rank < b.rank):
        c := mergeSub(a, b.l).
        if (b.color = 黒 and c.color = 赤 and c.l.color = 赤):
            if (b.r.color = 黒):
                return node(c.l, node(c.r, b.r, 赤), 黒).
            else:
                return node(node(c.l, c.r, 黒), node(b.r.l, b.r.r, 黒), 赤).
        else:
            return node(c, b.r, b.color).
    else if (a.rank > b.rank):
        c := mergeSub(a.r, b).
        if (a.color = 黒 and c.color = 赤 and c.r.color = 赤):
            if (a.l.color = 黒):
                return node(node(a.l, c.l, 赤), c.r, 黒).
            else:
                return node(node(a.l.l, a.l.r, 黒), node(c.l, c.r, 黒), 赤).
        else:
            return node(a.l, c, a.color).
    else:
        return node(a, b, 赤). 

この節の以降では，実装時に，疑問に思ったことをメモしておきます．興味がなければ読み飛ばしてもらって構いません．

場合分けについて

P. 18 の実装では，a.rank < b.rank（a.rank > b.rank） が確定したあとは，P.20, 21の2パターンとそれ以外の場合しか場合分けをしていません．実は，これで，条件を満たすために必要な操作がすべて列挙されています．

null チェックを行っていない点

この実装では，b の子および c の子の色を参照していますが，null チェックは必要ありません．

まず，b の子についてですが，a.rank < b.rank が成り立っておりa.rank >= 0 であることから b.rank >= 1であることがわかります．したがって，bは葉ではなく，条件6から，葉以外のノードは必ず2つの子を持つので，null チェックは不要です．

また，c については，少なくとも1つ赤のノードを挿入することから c 自身が null になることはなく，c を作成する時点で，a も b も null になり得ない（少なくとも葉まで到達した段階で a.rank == b.rank となる）ことから，c の子についても null チェックは不要であることがわかります．

c が赤の場合は一旦そのままにしている点

b が赤のノードの場合に，そのまま c を左の子とした場合に，赤のノードが連続し，条件4が満たされないままになる可能性があるように思えるかもしれません．

しかし，実際には以下の2通りしかなく，問題ありません．

1. b が根のとき，条件7からbを黒にすれば平衝条件を満たす．
2. b が根ではないとき，b と b の親の間には条件4が成り立っていることから，bの親は必ず黒であり，この場合，b の親の段階で平衝条件を満たすように変更が加わるため，問題ない．

c が赤の場合， c の右の子は黒で確定する点

まず，重要なポイントとして，a と b の rank が突然入れ替わることはないため，最初に a.rank < b.rank が成り立てば，a.rank == b.rank が成り立つまでは，常に，a.rank < b.rank が再帰的に成り立ちます．つまり，a.rank < b.rank の場合は，再帰的に b の左側の子に対して，a をマージする操作が繰り返されることになります．

さて，c が赤である場合を列挙してみると，

1. c が a.rank == b.rank のケースで新たに挿入されたノードの場合， rank の定義から，a.rank == b.rank となるとき， b は常に黒のノードなので c の右の子は黒．
2. c が P.21 のケースで赤に変更されたノードの場合，右の子は黒．(実際には左の子も黒なのでこのケースが問題になることはない)
3. a < b.l.rank で，a が b.l.l にマージされ，なおかつb.l.color == RED のとき，c.r == b.l.r であり，条件4から b.l.r は必ず黒．

Split

split 操作は，P. 24 の擬似コードをそのまま実装しても正しく動きません． 正確には，以下の擬似コードを実装する必要があります．

function split(a, k)
    if (k = 0):
        return <null, asRoot(a)>.
    if (k = a.size):
        return <asRoot(a), null>.
    if (k < a.l.size):
        <L, R> := split(a.l, k).
        return <L, merge(R, asRoot(a.r))>.
    else if (k > a.l.size):
        <L, R> := split(a.r, k - a.l.size).
        return <merge(asRoot(a.l), L), R>.
    else:
        return <asRoot(a.l), asRoot(a.r)>. 
        
function asRoot(a)
    if (a is null):
        return null.
    if (a.color = 黒):
        return a.
    else:
        return node(a.l, a.r, 黒).

正しく動かない原因は，条件2を満たさないためです．a.l, a.r は a から切り離した段階で独立した木になるため，戻り値として戻す，または，mergeする前の段階で，条件7を使って，根を黒にしておく必要があります．

計算量について

• merge: $O(|a.rank - b.rank|)$
• split: $O(\log n)$

RBSTと比較すると，葉にしか値を持たなかったり，追加の情報を保持しないといけなかったりと，定数倍が重そうなイメージですが，merge の計算量が$O(|a.rank - b.rank|)$なので，実際には insert や erase の操作のように似たような rank の木をくっつける場合には RBST より高速に動作する・・・はず．また，merge が$O(|a.rank - b.rank|)$なおかげで，線形時間で初期構築できます．(P.26参照)

あと，split において，merge を何回も呼び出しているのに $O(\log n)$ になるのは，非直感的かもしれません．split の操作は，再帰の各段階において，

• 左の部分木を L に merge する
• 右の部分木を R に merge する

のいずれかの操作を繰り返し行っているものと考えることができます．このとき，部分木は rank の小さい順に merge されていくため，マージの計算量が$O(|a.rank - b.rank|)$であることから，$O(\log n)$になります．（$1,2,5, \ldots \log n$ のようなソート済みの列があった時に隣接する要素の差の和は $O(\log n)$ にしかなりません．）