freebsd rb.h remove を読んでみよう 7

複雑な黒ノードの削除を見ていきましょう。 まずは削除されるノードにnilを入れます。

pathp->node = &rbtree->rbt_nil;

親が赤の場合から見ていきましょう。

f:id:yamshing:20151028193721p:plain

freebsdの実装では左が削除された場合と右が削除された場合にまず場合分けしています。

if (pathp->cmp < 0) {
//左の子が削除された
}else{
//右の子が削除された
}

その両方のケースで次のように親が赤であるかをチェックしています。

if (rbtn_red_get(a_type, a_field, pathp->node)) {
…
}

では左の子の場合から見ていきましょう。

assert(rbtn_red_get(a_type, a_field, pathp[1].node)		\
	      == false);						\
	    if (rbtn_red_get(a_type, a_field, pathp->node)) {		\
		a_type *right = rbtn_right_get(a_type, a_field,		\
		  pathp->node);						\
		a_type *rightleft = rbtn_left_get(a_type, a_field,	\
		  right);						\
		a_type *tnode;						\
		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)                                   */\
		    /*                                                */\
		    rbtn_black_set(a_type, a_field, pathp->node);	\
		    rbtn_rotate_right(a_type, a_field, right, tnode);	\
		    rbtn_right_set(a_type, a_field, pathp->node, tnode);\
		    rbtn_rotate_left(a_type, a_field, pathp->node,	\
		      tnode);						\
		} else {						\
		    /*      ||                                        */\
		    /*    pathp(r)                                    */\
		    /*  //        \                                   */\
		    /* (b)        (b)                                 */\
		    /*           /                                    */\
		    /*          (b)                                   */\
		    /*                                                */\
		    rbtn_rotate_left(a_type, a_field, pathp->node,	\
		      tnode);						\
		}							\
		/* Balance restored, but rotation modified subtree    */\
		/* root.                                              */\
		assert((uintptr_t)pathp > (uintptr_t)path);		\
		if (pathp[-1].cmp < 0) {				\
		    rbtn_left_set(a_type, a_field, pathp[-1].node,	\
		      tnode);						\
		} else {						\
		    rbtn_right_set(a_type, a_field, pathp[-1].node,	\
		      tnode);						\
		}							\
		return;	

親の右左の子で場合分けしています。 1と2のケースですね

		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)                                   */\
		    /*                                                */\
		    rbtn_black_set(a_type, a_field, pathp->node);	\
                    //親を黒にします。
		    rbtn_rotate_right(a_type, a_field, right, tnode);	\
      //右の子を中心に右回転します。そして新しい親をtnodeに入れます。
		    rbtn_right_set(a_type, a_field, pathp->node, tnode);\
      //その新しい親をpathpのノードの右につけます。
		    rbtn_rotate_left(a_type, a_field, pathp->node,	\
		      tnode);						\
      //pathpのノードを中心に左回転します。

ここが1のケースです

f:id:yamshing:20151028193956p:plain

この1のケースの場合親の赤を黒にできれば右の黒の数は変えずに左の削除された黒を補填することができます。 親の赤と右の子の黒を取り替えられればそれで完了するのですが右に赤が来られないのでこれはできません。 では親の赤を黒にしてしまいましょう。 そうすると右の黒が一つ多くなってしまいます。 ならば左に回転させたらどうでしょう。 これもダメです。

f:id:yamshing:20151028194119p:plain

なぜなら右の子の左の子が左の子の右の子になってしまうからです。 しかもこれでは左の黒がまた一つ多くなってしまいます。

よってまずは右の子を中心に右に回転してその右の赤が親になるように 左に回転しています。 これならば左に黒を一つ多く送らずに左回転ができ右に多くなった黒を一つ左に送ることができます。

2の場合はどうでしょう。

f:id:yamshing:20151028194219p:plain

} else {						\
		    /*      ||                                        */\
		    /*    pathp(r)                                    */\
		    /*  //        \                                   */\
		    /* (b)        (b)                                 */\
		    /*           /                                    */\
		    /*          (b)                                   */\
		    /*                                                */\
		    rbtn_rotate_left(a_type, a_field, pathp->node,	\
		      tnode);						\
                    //pathpのノードを中心に左回転させます。
		}

2の場合はただ左に回転すれば右側の黒を減らさずに左の黒を一つ多くできます。 これで完了です。

次は右の子の場合を見ていきましょう。

 } else if (rbtn_red_get(a_type, a_field, pathp->node)) {	\
		a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
		if (rbtn_red_get(a_type, a_field, leftleft)) {		\
		    /*        ||                                      */\
		    /*      pathp(r)                                  */\
		    /*     /        \\                                */\
		    /*   (b)        (b)                               */\
		    /*   /                                            */\
		    /* (r)                                            */\
		    a_type *tnode;					\
		    rbtn_black_set(a_type, a_field, pathp->node);	\
		    rbtn_red_set(a_type, a_field, left);		\
		    rbtn_black_set(a_type, a_field, leftleft);		\
		    rbtn_rotate_right(a_type, a_field, pathp->node,	\
		      tnode);						\
		    /* Balance restored, but rotation modified        */\
		    /* subtree root.                                  */\
		    assert((uintptr_t)pathp > (uintptr_t)path);		\
		    if (pathp[-1].cmp < 0) {				\
			rbtn_left_set(a_type, a_field, pathp[-1].node,	\
			  tnode);					\
		    } else {						\
			rbtn_right_set(a_type, a_field, pathp[-1].node,	\
			  tnode);					\
		    }							\
		    return;						\
		} else {						\
		    /*        ||                                      */\
		    /*      pathp(r)                                  */\
		    /*     /        \\                                */\
		    /*   (b)        (b)                               */\
		    /*   /                                            */\
		    /* (b)                                            */\
		    rbtn_red_set(a_type, a_field, left);		\
		    rbtn_black_set(a_type, a_field, pathp->node);	\
		    /* Balance restored. */				\
		    return;						\
		}							\
	    }

ここでも親の左左の子で場合分けしています。 3と4のケースですね

f:id:yamshing:20151028194338p:plain

3のケースを見てみましょう。 右に回転できればいいのですが右に赤が来てしまうのでできません。 それでは赤と子の黒を交換してみましょう。 そうすると左に赤赤のノードができてしまうので 左の子をまた黒に変えなければなりません。 これで左に一つ黒が多くなってしまうのでそれを右に回転させて右に遅れば左の黒が一つ減り 黒の数が等しくなります。

 } else if (rbtn_red_get(a_type, a_field, pathp->node)) {	\
		a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
		if (rbtn_red_get(a_type, a_field, leftleft)) {		\
		    /*        ||                                      */\
		    /*      pathp(r)                                  */\
		    /*     /        \\                                */\
		    /*   (b)        (b)                               */\
		    /*   /                                            */\
		    /* (r)                                            */\
		    a_type *tnode;					\
		    rbtn_black_set(a_type, a_field, pathp->node);	\
                     //親の赤を黒にします。
		    rbtn_red_set(a_type, a_field, left);		\
      //左の子を赤にします。
		    rbtn_black_set(a_type, a_field, leftleft);		\
                     //左の左の子を黒にします。
		    rbtn_rotate_right(a_type, a_field, pathp->node,	\
		      tnode);						\
                     //pathpのノードを中心に右回転します。
		   

f:id:yamshing:20151028194414p:plain

4のケースはどうでしょう。 親の赤と左の子の黒を交換すれば右の黒を一つ増やせて完了です。

 /*        ||                                      */\
		    /*      pathp(r)                                  */\
		    /*     /        \\                                */\
		    /*   (b)        (b)                               */\
		    /*   /                                            */\
		    /* (b)                                            */\
		    rbtn_red_set(a_type, a_field, left);		\
      //左の子を赤にします。

		    rbtn_black_set(a_type, a_field, pathp->node);	\
      //親を黒にします。

		    /* Balance restored. */				\
		    return;

次回は親が黒の場合を見てみましょう。