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

親が黒でその孫が赤の場合を見てみましょう。

f:id:yamshing:20151105181224p:plain

6番から見てみましょう。

右に一つ黒が足りないので右に回転させたらどうでしょう。

すると今度は左に一つ黒が足りなくなるので一つ黒を増やさなくてはなりません。

それは赤があるのでそれを黒にすることでできます。

コードで見てみましょう。

a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
		if (rbtn_red_get(a_type, a_field, leftleft)) {		\
		    /*               ||                               */\
		    /*             pathp(b)                           */\
		    /*            /        \\                         */\
		    /*          (b)        (b)                        */\
		    /*          /                                     */\
		    /*        (r)                                     */\
		    a_type *tnode;					\
		    rbtn_black_set(a_type, a_field, leftleft);		\
                     //左の左の子を黒に
		    rbtn_rotate_right(a_type, a_field, pathp->node,	\
		      tnode);
                     //右に回転

まず左の左の子ノードを黒にしてそれから右に回転させています。

f:id:yamshing:20151105181230p:plain

7番はどうでしょう。

f:id:yamshing:20151105181238p:plain

左に回転できるでしょうか。

このまま左に回転させると右の左の子の赤が左の黒の子に つけられてしまい右に黒を一つ増やすための赤がなくなってしまいます。

なのでまずは赤のノードを右に回転させてから全体を左に回転させます。

そしてその赤のノードを黒にすれば左に黒を送りながら右の枝に黒を一つ増やすことができてしまいます。

f:id:yamshing:20151105181245p:plain

コードで見てみましょう。

a_type *right = rbtn_right_get(a_type, a_field,		\
		  pathp->node);						\
		a_type *rightleft = rbtn_left_get(a_type, a_field,	\
		  right);						\
		if (rbtn_red_get(a_type, a_field, rightleft)) {		\
		    /*      ||                                        */\
		    /*    pathp(b)                                    */\
		    /*  //        \                                   */\
		    /* (b)        (b)                                 */\
		    /*           /                                    */\
		    /*          (r)                                   */\
		    a_type *tnode;					\
		    rbtn_black_set(a_type, a_field, rightleft);		\
                     //右の左の子を黒に
		    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);
                     //全体を左に回転

次回は子ノードが赤の場合を見ていきましょう。