親が黒の場合を見てみましょう。 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 follo…

複雑な黒ノードの削除を見ていきましょう。 まずは削除されるノードにnilを入れます。 pathp->node = &rbtree->rbt_nil; 親が赤の場合から見ていきましょう。 freebsdの実装では左が削除された場合と右が削除された場合にまず場合分けしています。 if (pathp…

今回は 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, path…

今回はrb.hのremoveを読んでいきましょう a_attr void \ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ struct { \ a_type *node; \ int cmp; \ } *pathp, *nodep, path[sizeof(void *) << 4]; \ /* Wind. */ \ nodep = NULL; /* Silence compile…

削除を見ていきましょう。赤ノードの削除は何も変わらないので無視できます。削除されるのが黒ノードの場合削除された黒ノードを補うために赤ノードを黒に変えていきます。そうなのでその変える赤の位置で場合分けしていきます。では見てみましょう。 親が赤…

rb.hのinsertをrubyで書いてみました。 https://github.com/yamshing/code_reading/blob/master/rb.rb ●が赤で○が黒です。遊んで見てください。

前回は左に赤が二つつながる場合を見ました。 http://yamshing.hatenablog.com/entry/2015/09/30/205603 今回は右に赤が来る場合です。 では読んでみましょう。 a_type *right = pathp[1].node; //次のノードを rbtn_right_set(a_type, a_field, cnode, righ…