freebsd rb.h remove を読んでみよう 8
親が黒の場合を見てみましょう。
6パターンあります。 この中でまず赤がないものを見てみましょう。
if (pathp->cmp < 0) { \
\
if (rbtn_red_get(a_type, a_field, pathp->node)) { \
\
if (rbtn_red_get(a_type, a_field, rightleft)) { \
/* In the following diagrams, ||, //, and \\ */\
/* indicate the path to the removed node. */\
/* */\
/* || */\
/* pathp(r) */\
/* // \ */\
/* (b) (b) */\
/* / */\
/* (r) */\
/* */\
} else { \
/* || */\
/* pathp(r) */\
/* // \ */\
/* (b) (b) */\
/* / */\
/* (b) */\
/* */\
\
} \
… \
return; \
} else { \
\
if (rbtn_red_get(a_type, a_field, rightleft)) { \
/* || */\
/* pathp(b) */\
/* // \ */\
/* (b) (b) */\
/* / */\
/* (r) */\
\
\
return; \
} else { \
//------------------------------------
//************ここが８***************
//-----------------------------------
/* || */\
/* pathp(b) */\
/* // \ */\
/* (b) (b) */\
/* / */\
/* (b) */\
a_type *tnode; \
rbtn_red_set(a_type, a_field, pathp->node); \
rbtn_rotate_left(a_type, a_field, pathp->node, \
tnode); \
pathp->node = tnode; \
} \
} \
} else { \
if (rbtn_red_get(a_type, a_field, left)) { \
\
if (rbtn_red_get(a_type, a_field, leftrightleft)) { \
/* || */\
/* pathp(b) */\
/* / \\ */\
/* (r) (b) */\
/* \ */\
/* (b) */\
/* / */\
/* (r) */\
} else { \
/* || */\
/* pathp(b) */\
/* / \\ */\
/* (r) (b) */\
/* \ */\
/* (b) */\
/* / */\
/* (b) */\
} \
\
return; \
} else if (rbtn_red_get(a_type, a_field, pathp->node)) { \
if (rbtn_red_get(a_type, a_field, leftleft)) { \
/* || */\
/* pathp(r) */\
/* / \\ */\
/* (b) (b) */\
/* / */\
/* (r) */\
return; \
} else { \
/* || */\
/* pathp(r) */\
/* / \\ */\
/* (b) (b) */\
/* / */\
/* (b) */\
return; \
} \
} else { \
if (rbtn_red_get(a_type, a_field, leftleft)) { \
/* || */\
/* pathp(b) */\
/* / \\ */\
/* (b) (b) */\
/* / */\
/* (r) */\
\
return; \
} else { \
//------------------------------------
//************ここが5***************
//-----------------------------------
/* || */\
/* pathp(b) */\
/* / \\ */\
/* (b) (b) */\
/* / */\
/* (b) */\
rbtn_red_set(a_type, a_field, left); \
} \
} \
} \
}
rb.hのコードの骨格を見てみるとこの赤の無いケースには 共通点があります。
それは他のケースはreturnが来ているのにこの二つのケースはreturnしていないということです。
ではどんな変更をしているのでしょうか。
簡単そうな5から見てみましょう。
５では左の子を赤にしています。
これは何を意味しているのでしょうか。
右側は黒が一つ減っているところに左側も黒を赤にして黒を一つ減らしています。
つまり今の親ノードの両方のこの黒を一つ減らしたということになります。
そしてこれがreturnしないわけなのです。
この時点ではまだ黒の数が均衡していない状態は続いています。
なのでreturn せず木を一つ上に登って解決しようとしているのです。
ここでreturnせずにコードが実行されると
for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) {
このfor loop によってpathpが一つ上に上がり(ルートに近づく)ます。
すると今の親ノードを削除されたノード(黒が一つ足りないノード)とみなして また１０通りのパターンのどれかに当てはまるかを見ることができます。
つまり左の黒を赤に変えて両方の子ノードを一つ黒が足りない状態にして 一つ上のノードで赤がどこかにあるパターンに当てはめようとしているのです。
８番は少し複雑になりますがアイデアは同じです。
左の黒が減ったので右も黒を減らそうとします。
右側は赤になりえないので親ノード自身を赤にします。
しかし親ノードを赤にしたことでさらに左のノードでも一つ黒が足りなくなってしまいます。
なので左に回転して右の黒を親にして左の黒だけ一つ増やしています。
これで両方のノードが黒が一つ足りない状態になり木を一つ上に登り 赤のあるパターンに当てはまるかをチェックしていきます。
次回もこの黒が親の別のパターンを見ていきましょう。
