最後のパターンになります。 どうすればいいでしょうか。 黒を増やすためには方法は一つしかありません。 それは赤を黒に変えることです。(*1) もちろんこれでは左の黒が増えてしまうので回転させて右にそれを持っていかなくてはなりません。(*2) これで右の…

親が黒でその子が赤の場合を見てみましょう。これが最後のパターンになります。 このパターンは更にひ孫に赤があるかどうかで場合分けできます。 ９番のひ孫に赤があるパターンから見ていきましょう。 まず最初に気になることは子が赤でひ孫が赤のパターンは…

親が黒でその孫が赤の場合を見てみましょう。 6番から見てみましょう。 右に一つ黒が足りないので右に回転させたらどうでしょう。 すると今度は左に一つ黒が足りなくなるので一つ黒を増やさなくてはなりません。 それは赤があるのでそれを黒にすることででき…

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

前に赤黒木に挿入するときは赤が２つ来るのを防ぐように調節すると書きました。 それがfreebsdのmallocではどのように実装されているのかを見てみましょう。 freebsdは9.3です。rb.hは/usr/src/lib/libc/stdlib内にありますね。 a_attr void \ a_prefix##ins…

ちょっと複雑な挿入 前回挿入をしたのはいつも大きい数字だったので比較的 単純にいきました。今度は少し複雑な挿入をやってみよう。 ルール 赤の子に赤が来ることはできない。 赤の子に赤が来るパターンとはどのようなものでしょうか？ 赤の右の子が赤 赤の…

赤黒木のルールは ルートは常に黒 新ノードは赤で右に追加 右下の子だけが赤の時左回り 両方の子が赤の時上下の色を変える まずはルートに２を挿入 右下が赤なので左回り。 ルートは黒に 次のノードを挿入 両方の子が赤なので色を交換 ルートは黒に ノードを…