赤黒木 (18)

gauche

delete_node1 手続き掘削。ええと手続き定義なコメントにもあるように

/* deletes a node TODIE who has at most one child, CHILD.
   Note that CHILD can be NULL (empty BLACK node) */

この手続きが呼び出される時点で両方子供が居るケイスはあり得ない形になってます。つうか swap_node がワケワカになってます。前の要素と swap て

  B:-3
B:0
  B:5
      B:6
    B:8
      B:9

で B:5 が削除対象だと B:0 と swap だったり

    B:2
      B:3
  B:4
B:5

で B:5 が削除対象だと B:4 と swap だったりするけど、何か思考のドロ沼にハマッていたりするのだろうか。

ドロ沼

むむむ、と頭を痛めておったのですが、これそもそもが左右両方子供がいる、が前提じゃんか。つうことは交換対象になる要素は左の子供は居るけど右の子供は居ない、という事になるのか。やれやれ。
この swap のおかげで delete_node1 が呼び出される瞬間、削除対象の n という要素は右又は左にのみ子供がいる、または子供が居ない、という状態というコメントにある通りの状態になる、と。このあたり昨日はちゃんとイメージできてたんですが、完全に忘却の彼方に去ってました。

delete_node1 手続き

赤なら黒ノードのカウントは変わらないのでそのままで良いのか。shiro さん実装だと、

  • 削除対象のノードの親と子供のリンクをはり直す
  • 削除対象ノードが赤なら終わり
    • 削除対象ノードから出てるリンクは delete_node 手続きでナニ
  • 削除対象ノードの子供が赤なら黒にして終わり

この時点で子供は居ないか左右のどちらか、という状態にしているというのは分かりやすいですね。また、この時点で削除対象ノードも子供も黒確定のはず。

    replace_node(tc, todie, child);
    if (REDP(todie)) { DELETE_CASE("1"); return; }
    if (REDP(child)) { DELETE_CASE("2"); child->color = BLACK; return; }

  recur:
    /* At this point, child is BLACK. */

次のケイスは削除対象が root な要素だった場合か。

    if (parent == NULL) { DELETE_CASE("3"); return; }

このあたりまでであれば rbtree.scm な該当箇所も見極め可能。例えば case 1. が delete-node! の以下だし

      (when (black? z)
        (delete-fixup! tree x p))

case 2. は delete-fixup! で以下な分岐。

    (if (or (nil? p) (red? x))
      (unless (nil? x)
        (paint-black! x))

ちなみに上記の条件式は case 3. にも当てはまりますね。
で、次の記述なんですが以下。

    sibling = SIBLING2(parent, child);
    /* sibling can't be NULL, since it would break the invariance of
       consistent # of black nodes for every path. */
    SCM_ASSERT(sibling != NULL);

コメントは以下なカンジなのかな。

全パスの黒ノードの数の一貫性を失なうので、sibling は NULL にはできない

どーゆー事かというと

any:x
    B:y
      B:z

みたいな部分木の key が y な node を削除する場合、たしかに y の兄弟は居ないと黒のカウント的に計算が合わない。また、この時点で自分が赤、子供が赤な可能性は無い。
で、削除対象の兄弟が赤だった場合の処理が以下。

    if (REDP(sibling)) {
        parent->color = RED;
        sibling->color = BLACK;
        if (LEFTP2(parent, child)) {
            rotate_left(tc, parent);
            sibling = SIBLING2(parent, child);
            DELETE_CASE("4a");
        } else {
            rotate_right(tc, parent);
            sibling = SIBLING2(parent, child);
            DELETE_CASE("4b");
        }
    }

これは delete-fixup! の最初の let の中にある if 分岐の中身ですね。

      (let1 b (eq? x (left p))
        (let1 w (let1 w (right* p b)
                  (if (red? w)
                    (begin (paint-black! w)
                           (paint-red! p)
                           (left-rotate! tree p b)
                           (right* p b))
                    w))

case 4a. と 4b. は右か左かで決まるのか。
つうか、左右の切り分けを b で、ってのは格好良いですね。そしてこの時点で削除対象の兄弟ノードは黒確定。

    /* At this point, sibling is BLACK */

なんかコメントのお陰でとても分かりやすいです。で、次に出てくるのが case 5. な模様。

    if (BLACKP(parent) && BLACKP(sibling->left) && BLACKP(sibling->right)) {
        sibling->color = RED;

        child = parent;
        parent = parent->parent;
        DELETE_CASE("5");
        goto recur;
    }

これは何か、というと削除対象の親が黒で兄弟ノードの子供が両方黒。これ、scheme な実装だと以下な部分にあたるのか。

          (if (and (black? (left w)) (black? (right w)))
            (begin (paint-red! w)
                   (loop p (parent p)))

なんで shiro さん実装は parent が黒かどうかを判定しているんだろ。とは言え、case 5. な試験のソレは以下な記述ですね。

case 5.  deleting black node, whose parent and sibling is black and sibling's both child is black.

実は次に出てくる case 6. が parent が赤で sibliing の子供が両方黒なケイスになってますね。試験なソレが以下。

case 6.  deleting red node w/ both children

あ、これって

          (if (and (black? (left w)) (black? (right w)))
            (begin (paint-red! w)
                   (loop p (parent p)))

の後の

  (let loop ((x x) (p p))
    (if (or (nil? p) (red? x))
      (unless (nil? x)
        (paint-black! x))

の部分が云々、なのか。でもなんとなく試験なコメントが微妙な気がするな。つうか、赤な node の子供が両方居る状態ってのはどういった状態なんだろ。
scheme 実装と shiro さん実装から類推するに

  B:c
B:a
    B:e
  R:b
    B:d

B:d または B:e が削除対象の場合、以下に変換するのか。(B:e を削除対象としてみます)

  B:c
B:a
  B:b
    R:d

これで平衡を保ってますね。試験のコメントが微妙かも。

case 6.  deleting black node, whose parent is red and sibing is black.

なのかなぁ。

続きは

#台風そん で、ということにして今日はこのあたりで。