freebsd rb.h remove を読んでみよう 6
今回は
if (pathp->node != node) {
この条件のelseの部分です。 ここがelseとなるにはこの前の部分で
if (cmp < 0) { \ pathp[1].node = rbtn_left_get(a_type, a_field, pathp->node); \ } else { \ pathp[1].node = rbtn_right_get(a_type, a_field, pathp->node); \ if (cmp == 0) { \ pathp->cmp = 1; \ nodep = pathp; \ for (pathp++; pathp->node != &rbtree->rbt_nil; pathp++) {\ pathp->cmp = -1; \ pathp[1].node = rbtn_left_get(a_type, a_field, pathp->node); \ } \ break;
後ろのfor loopに入らないことです。そのためにはpathp++のnodeがnilである必要があります。 つまりpathp[1].node( pathp->nodeの右の子)がnilであるということです。
右側の子がnilであるならというのが条件です。 この条件の中身を見ていきましょう。
a_type *left = rbtn_left_get(a_type, a_field, node); \ //左の子を見ます。 if (left != &rbtree->rbt_nil) { \ //もし左の子がnilでないなら /* node has no successor, but it has a left child. */\ /* Splice node out, without losing the left child. */\ assert(rbtn_red_get(a_type, a_field, node) == false); \ assert(rbtn_red_get(a_type, a_field, left)); \ //ここでassertが入ります。 //削除されるノードが赤でないこと //その左の子が赤であることを確認しています。 //確かに右に子がなく左には子があるとしたらその子は黒にはなりえません。 //そうでないと右の子と左の子の間に黒の数の違いがあったことになり //木が不均衡であったことになってしまいます。 rbtn_black_set(a_type, a_field, left); \ //左の子を黒にします //これで削除された黒の数を補ました。 //そしてこの左の子をpathpにつないでいきます。 //もしpathpがpath配列の先頭ならrootに //そうでないならpathpの一つ前のノードの子にセットします。 if (pathp == path) { \ rbtree->rbt_root = left; \ } else { \ if (pathp[-1].cmp < 0) { \ rbtn_left_set(a_type, a_field, pathp[-1].node, \ left); \ } else { \ rbtn_right_set(a_type, a_field, pathp[-1].node, \ left); \ } \ } \ return; \
後半のelseは左の子がnilならということです。 右がnilで左もnilということです。 この時もしpathpがpath配列の先頭ということはどういうことでしょう。
} else if (pathp == path) { \ /* The tree only contained one node. */ \ rbtree->rbt_root = &rbtree->rbt_nil; \ return; \ } \
コメントにあるようにこの木には一つのnodeしかないということです。 そしてそれが削除されるのでrootにnilを入れて終わりです。
最後にもう一つチェックします。
if (rbtn_red_get(a_type, a_field, pathp->node)) { \ /* Prune red node, which requires no fixup. */ \ assert(pathp[-1].cmp < 0); \ //赤のノードは常に左 rbtn_left_set(a_type, a_field, pathp[-1].node,&rbtree->rbt_nil); //削除されるノードは左なのでそこにnilをセット \ return; \ }
それは削除されるノードが赤の場合です。この場合は簡単です。 削除されるノードをnilに変えるだけで終わりです。
今回は
- 左に赤の子があるノード
- 子がないノードでrootであるノード
- 赤ノード
の削除を行いました。
これらは単純な削除のケースです。 次回はいよいよ複雑な黒ノードの削除に入ります。