赤黒木 (17) - yamanetoshi's diary

朝練メモおよびその後の現実トウヒなメモ。昨晩のショックは相当大きいのですが。

とりあえず

木構造な情報を出力するソレが欲しい。つうか util.rbtree は export されてる手続きが必要最低限に抑えられててかなり辛い。やはり原理をきちんと理解して試験を確認する以外に良い手立ては無いのかなぁ。

整理してみる

乗り掛った船なので (何
例えば left-rotate! に渡す boolean な引数が #t の場合だと x として渡す要素の右側にある要素 (y) と場所を交換する形になります。

y は x の右側の要素だった
x は y の左側の要素になった
- y の左側の要素が x の右側要素になった

これが b が #f の場合だと x として渡す要素の左側にある要素 (y) と場所を交換する形になる訳か。

y は x の左側要素だった
x は y の右側要素になった
- y の右側要素が x の左側要素になった

これを踏まえて諸々確認

追加から。追加の処理は割と簡単に考えることができるらしく、基本的には追加されるべき末端に赤い node として追加されて、put-fixup! に更新された tree と追加された node が渡されます。
put-fixup! では追加された node の親が赤だった場合に、という手続きの記述がメインになってます。その中で b と y というローカル変数の設定してるんですが

b は z の親がそのまた親の左側要素だったら真
y は z の親の対向側の要素

という形になっている模様。で、親の対向要素が赤だった場合 (これは z も赤でその親も赤で、その兄弟も赤という形になります)、親とその兄弟は黒にされて (z はそのまま赤)、z の親のそのまた親が赤になって繰り返すのか。なんとなく思い出してきた。
ちょっとマンガで控えを。このケイスは以下なカンジで

    R:  <- 追加された node
  R:
B:
  R:

以下になって上の部分木のてっぺんを loop に渡すのか。

    R:  <- 追加された node
  B:
R:
  B:

で、てっぺんの親が赤でなければこのまま終わります。そうでなければ下記 else なブロックで云々、ということになるのか。
で、else なブロック (z の親の兄弟は黒) では例えば

  R:0
    R:0.5
B:1

みたいな部分木 (z は B:0.5 な node) になっていたら

    R:0
  R:0.5
B:1

みたいに直線に直して (z は B:0 になる) 云々、ということをしてたはず。で、色を以下に変えて

    R:0
  B:0.5
R:1

right-rotate! で以下になるはず。

  R:0
B:0.5
  R:1

なんかだんだん追加は比較的簡単だったことを思いだしつつあったりして。そして追加のコストはたしかに O(logN) つうのはイメージできます。

削除か

なんどか追いかけてるのでなんとなく読めてはいるんですがどうなるか。
node を削除するにあたって

左右の子供の要素が両方ある
右又は左の片側のみ
子供なし

子供が両方いるケイスについては

削除対象 node より_大きい_要素があればその次にあたる要素
削除対象 node より_大きい_要素がなければ_小さい_もののうち最大の要素

と置きかえられ、削除対象はその要素となります。基本的にみ右側 (_大きい_と表現) の部分木にそれが存在する場合、末端要素となるはずであり、左側 (_小さい_と表現) の部分木にそれが存在する場合には子供の要素が存在したとしても左側にしか無いはず、なのかどうなのか。
いずれにしても

  (let1 z (if (and (not (nil? (left z))) (not (nil? (right z))))
            (let1 y (successor z)
              (set! (ref z 'key) (ref y 'key))
              (set! (ref z 'value) (ref y 'value))
              y)
            z)

以降は z の子供な要素が左右そろっている、ということは無いはず、なので

    (let ((x (left* z (not (nil? (left z)))))

のような形で片側から取り出す、ということをしている模様。切り取る要素が決まったら基本的に

親子関係の更新
自分から出ているリンクを破棄

ということをしてます。あ、親からのリンクを張る処理も面白いですね。

        (set! (left* p (eq? z (left p))) x))

p は nil ではない前提なんですが z とその親 (p) の関係によって p と z の子供 (x) の関係が決定されております。
そして、親子関係を更新した直後 (他から削除対象へのリンクは全て除去されている)、削除対象の要素が黒の場合、delete-fixup! という手続きを呼び出しております。ある意味ここが核心。

delete-fixup! 手続き

渡しているのは、削除対象の子供の要素 (x) と削除対象の親の要素 (p) なのか。つうか、基本的に削除対象の要素は上に書いた通り、外部からのリンクは全て切られているのでここではそれを気にする必要はない、と。
つうかこれ、やっぱ難しい。実例見ながら、の方が良いのかどうか。ちょっとテストケイスのソレを列挙してみます。

case 1. deleting the leaf red node.
case 8a. deleting the leaf black node. parent is red, sibling is black.
case 8b. same, except left/right swapped
case 6. deleting red node w/ both children
case 2. deleting black node, whose parent is black and sibing is red.
case 5. deleting black node, whose parent and sibling is black and sibling's both child is black.
case 7a deleting black node, which is a left child of its parent, and its sibling is black, and sibling's left child is red.
- This goes through a nested if-statement in delete_node1() and involves swapping sibling.
case 4b. deleting black node, whose sibling is red.
case 3. this goes through parent==NULL stop condition in the loop in delete_node1.
case 4a. the reverse case of 4b.

なんとなくこれを元にするってことは shiro さんの実装も見ないとダメな気がしてきています。

src/treemap.c

追加はスルーで削除のみ。おおよそヤッてることはイメージできるんですが、rui さんの実装とほぼ同じに見えます。ただ、削除対象要素の両方に子供が居る場合、

    while (n->left && n->right) {
        /* N has both children.  We swap N and its previous node.
           It would be easier just to swap key and value, but it could
           lead to a hard-to-track bug if a pointer to N is retained
           in somewhere (e.g. iterator).  So we actually swap the node. */
        swap_node(tc, n, prev_node(n));
    }

なカンジで key と value だけではなくてリンクを貼り替えたりしてますが詳細は上のコメントでナニ。とは言え successor と prev_node が違う挙動に見えます。

prev_node は削除対象の一つ_前_の要素を戻すけどそれが無ければ NULL
successor は削除対象の一つ_後_の要素を戻すけどそれが無ければ一つ_前_になるのか
- とは言え探索失敗したら NULL を戻します

成程。このあたりの微妙な差がアレなのか。で、核心は delete_node1 手続きなんですが、確認は別途ということにさせて下さひ。