赤黒木 (19) #台風そん
理解がアレなので整理しつつ再確認。つうか風が凄い。昼頃最接近らしいのでそれまで何も無いことを切に願う。
とりあえず兄弟が赤だった場合のソレ。例えば以下なケイス。
/* rotate_left:
N R
+-----+ +-----+
L R ==> N GR
+---+ +---+
GL GR L GL
*/ええと、replace_node の後なので parent が N で child が L で、R な node が赤の場合、ということになります。この場合、GL および GR は黒になるので回転後、L の兄弟は黒確定ですね。
ちなみに、この時点まで親の色はノーチェックなんですが、例えば上のケイスだと R は黒になって parent の N が赤になりますね。回転後の GL が sibling になってその子供は両方黒なので、このケイスが正に
if (REDP(parent) && BLACKP(sibling->left) && BLACKP(sibling->right)) {の case 6. になるのか。でもやはり何かがおかしい。つうか上の図ベースで考えてるから微妙なんだろうな。
試験を確認
case 6. なナニ。以下から
;; B:-3 => -3 ;; R:-2 => -2 ;; B:-1.5 => -1.5 ;; B:0 => 0 ;; B:1.5 => 1.5 ;; R:2 => 2 ;; B:3 => 3
R:2 な要素を削除したら以下になるとのこと。
;; B:-3 => -3 ;; R:-2 => -2 ;; B:-1.5 => -1.5 ;; B:0 => 0 ;; B:1.5 => 1.5 ;; R:3 => 3
コメントがアレ。
;; case 6. deleting red node w/ both children ;; In our implementation, the node is first replaced by ;; its previous node until we get a single-child case, ;; then the balancing is applied. In this particular case ;; it degenerates to the deletion of a black node whose ;; parent is red and whose sibling is black.
記述だけ見ると確かに case 6. ですね。ただ、ソースを睨んでるのですが、何がどうなってそうなるのかが分からずどハマり状態。
delete_node1 手続きに渡されたときに以下な状態なのかどうなのか。
;; B:0 => 0 ;; R:1.5 => 1.5 ;; B:3 => 3
R:1.5 が parent で B:3 が sibling で、なのかどうなのか。つうか、swap_node でどうなるのか、というあたりでスデに微妙。
よく考えてみるに
停電してからでは遅いしこの袋小路から出れそうにないのでエントリ投入。
その後
うーむ、やはりコメント見るに_In this particular case it degenerates to the deletion of a black node whose parent is red and whose sibling is black._てどこでこうなるんだろ。さっぱり分からんぞ。
つーかそもそも的に隣同士の node な swap がアレなんですが困ったなぁ。
あ、落ち着いて確認してみたら当り前だけどちゃんと動くじゃん。しかもこうなりますね。
;; B:0 => 0 ;; B:2 => 2 ;; R:1.5 => 1.5 ;; B:3 => 3
削除対象が B:2 で云々。つうか swap て色も交換なんだ。隣同士だと上手く動きそうにない、という先入感と気圧が邪魔をした模様。そういえば util.rbtree の実装も色はそのまんまにしてたな。
え、てゆーことは delete-fixup! の
(if (or (nil? p) (red? x))
(unless (nil? x)
(paint-black! x))を通過するケイスとゆーのは左右に子供を持つ赤 node を削除する場合、のソレになるのか。随分見渡せるようになってきた感がありますが、そろそろ停電かも。
deletion case 7a
残りは 7 および 8 な模様。7a な試験のコメントが以下。
;; case 7a deleting black node, which is a left child of its parent, ;; and its sibling is black, and sibling's left child is red. ;; This goes through a nested if-statement in delete_node1() ;; and involves swapping sibling.
ええと、部分木てきに以下らしい (削除前)。削除対象は B:-2 なソレです。
;; B:-2 => -2 ;; R:-1.5 => -1.5 ;; R:-1 => -1 ;; B:-0.5 => -0.5 ;; B:0 => 0
コメントの通りな状態ですね。ええと、以下な状態になって rotate_right なのかな。
;; R:-1.5 => -1.5 ;; B:-1 => -1 ;; R:-0.5 => -0.5 ;; B:0 => 0
これはこうなるんかな。
;; R:-1.5 => -1.5 ;; B:-1 => -1 ;; R:-0.5 => -0.5 ;; B:0 => 0
で、sibling が B:-1 な要素になるんですがこれ、まだ続きがないとアレ。ちなみに parent は R:-1.5 ですよね。なので
sibling->color = parent->color;
parent->color = BLACK;これで以下なカンジになって
;; B:-1.5 => -1.5 ;; R:-1 => -1 ;; R:-0.5 => -0.5 ;; B:0 => 0
parent の左が child なので
if (LEFTP2(parent, child)) {
sibling->right->color = BLACK;
rotate_left(tc, parent);
DELETE_CASE("8a");こうなって rotate_left されるのか。
;; B:-1.5 => -1.5 ;; R:-1 => -1 ;; B:-0.5 => -0.5 ;; B:0 => 0
これはこうなるんですね。
;; B:-1.5 => -1.5 ;; R:-1 => -1 ;; B:-0.5 => -0.5 ;; B:0 => 0
これで平衡になった感。ちなみに 7b な条件ってのは
- 削除 node は黒で parent の右
- parent の右が child
- sibling->left が黒
- sibling->right が赤
つうことは deletion case5 直後の以下に
;; B:-2 => -2 ;; R:-1.5 => -1.5 ;; B:0 => 0 ;; R:0.5 => 0.5 ;; B:1 => 1 ;; B:2 => 2 ;; B:2.5 => 2.5 ;; B:3 => 3 ;; B:3.5 => 3.5 ;; R:4 => 4
- 0.5 を追加して
;; B:-2 => -2 ;; R:-1.5 => -1.5 ;; B:-0.5 -> -0.5 ;; B:0 => 0 ;; R:0.5 => 0.5 ;; B:1 => 1 ;; B:2 => 2 ;; B:2.5 => 2.5 ;; B:3 => 3 ;; B:3.5 => 3.5 ;; R:4 => 4
- 1.7 を追加するとこうなる?
;; B:-2 => -2 ;; R:-1.7 ;; R:-1.5 => -1.5 ;; B:-0.5 -> -0.5 ;; B:0 => 0 ;; R:0.5 => 0.5 ;; B:1 => 1 ;; B:2 => 2 ;; B:2.5 => 2.5 ;; B:3 => 3 ;; B:3.5 => 3.5 ;; R:4 => 4
これで B:-0.5 を削除したら 7b なソレになるのかどうか。
- sibling は赤ではない (case 4* ではない)
- parent は赤 (case 5 ではない)
- sibling の子供の片方が赤 (case 6 ではない)
- 親の右側要素 (case 7a ではない)
- sibling の左が黒で右が赤 (case 7b)
どうなるのかな。とりあえず -0.5 が落ちて
;; B:-2 => -2 ;; R:-1.7 ;; R:-1.5 => -1.5 ;; B:0 => 0
B:-2 の要素が赤になって R:-1.7 の要素の色が黒になって
;; R:-2 => -2 ;; B:-1.7 ;; R:-1.5 => -1.5 ;; B:0 => 0
sibling を基に rotate_left します。これはこうなるのか。
;; R:-2 => -2 ;; B:-1.7 ;; R:-1.5 => -1.5 ;; B:0 => 0
で、sibling が B:-1.7 になって 8b を通過。の前に色が以下になる。
;; R:-2 => -2 ;; R:-1.7 ;; B:-1.5 => -1.5 ;; B:0 => 0
で、sibling->left の色を黒にして
;; B:-2 => -2 ;; R:-1.7 ;; B:-1.5 => -1.5 ;; B:0 => 0
rotate_right を parent (B:-1.5) を基に呼ぶと
;; B:-2 => -2 ;; R:-1.7 ;; B:-1.5 => -1.5 ;; B:0 => 0
いやはや。7* は通過しない 8 の確認をしたくはありますが、ちょっと休みます。
case 8[ab].
調子が悪すぎて休めないようなので確認続行。8[ab] の試験は以下が起点。
;; R:-3 => -3 ;; B:-2 => -2 ;; R:-1.5 => -1.5 ;; B:-1 => -1 ;; B:0 => 0 ;; B:1 => 1 ;; R:1.5 => 1.5 ;; B:2 => 2 ;; R:3 => 3
ここから B:1 を削除する模様。
- 削除対象は黒 node
- sibling は B:2 で赤ではない (case 4* ではない)
- 親が赤 (case 5 ではない)
- sibling の片方が赤 (case 6 ではない)
- 親から見て左側だが、sibling の左側は赤ではない (case 7* ではない)
ということで親から見て左側なので 8a ですね。部分木てきには以下。
;; B:0 => 0 ;; R:1.5 => 1.5 ;; B:2 => 2 ;; R:3 => 3
sibling な B:2 が赤になって parent な R:1.5 が黒に
;; B:0 => 0 ;; B:1.5 => 1.5 ;; R:2 => 2 ;; R:3 => 3
で、sibling->rignt な R:3 が黒になって
;; B:0 => 0 ;; B:1.5 => 1.5 ;; R:2 => 2 ;; B:3 => 3
parent な B:1.5 を基に rotate_left します。
;; B:0 => 0 ;; B:1.5 => 1.5 ;; R:2 => 2 ;; B:3 => 3
次は 8b で削除したら以下になってて
;; R:-3 => -3 ;; B:-2 => -2 ;; R:-1.5 => -1.5 ;; B:-1 => -1 ;; B:0 => 0 ;; B:1.5 => 1.5 ;; R:2 => 2 ;; B:3 => 3
B:-1 な要素を削除。
- 末端黒要素の削除
- 親は赤
- sibling は黒で子供の片方赤
- 削除対象要素は親から見て右
- sibling の左側要素が赤
ということで 4 から 7 は全てスルーとなります。8a と同様に sibling の色を親の色にして親の色を黒に
;; R:-3 => -3 ;; R:-2 => -2 ;; B:-1.5 => -1.5 ;; B:0 => 0
で、sibling->left な R:-3 の色を黒にして
;; B:-3 => -3 ;; R:-2 => -2 ;; B:-1.5 => -1.5 ;; B:0 => 0
right_rotate で以下に、ということか。
;; B:-3 => -3 ;; R:-2 => -2 ;; B:-1.5 => -1.5 ;; B:0 => 0
削除処理の掘削完了。別エントリで纏めを作ります。
