赤黒木 (21)
昨晩、以下をトレイス中に力尽きた模様。
以下を再度確認してみます。
;; preparation ;; B:-2 => -2 ;; R:-1.5 => -1.5 ;; R:-1 => -1 ;; 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 (i -0.5 -1) ;; 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. (test* "deletion case7a" #t (begin (d -2) (c))) ;; case 4b. deleting black node, whose sibling is red. (test* "deletion case4b" #t (begin (d 0.5 1) (c))) ;; case 3. this goes through parent==NULL stop condition in the ;; loop in delete_node1. ;; B:-1.5 => -1.5 ;; R:-0.5 => -0.5 ;; B:0 => 0 ;; B:2.5 => 2.5 ;; R:3 => 3 ;; B:3.5 => 3.5 ;; R:4 => 4 (test* "deletion case3" #t (begin (d 2 -1) (c)))
纏め作りたいんだけどなぁ。とは言え、台風云々のおかげかどうか不明ですが、色々な意味でへろへろ。これから台風が、という方々におかれましてはくれぐれもご注意下さい。そしてあまり被害がないことを祈っております。
最初から再開
まず最初の状態から B:-2 な要素の削除。確かにケイス的に 7a ですね。sibling な B:-0.5 が赤になり、その左側の子供の色が黒になって rotate_right される模様。
;; R:-1.5 => -1.5 ;; B:-1 => -1 ;; R:-0.5 => -0.5 ;; B:0 => 0
R:-0.5 を基に rotate_right なので以下か
;; R:-1.5 => -1.5 ;; B:-1 => -1 ;; R:-0.5 => -0.5 ;; B:0 => 0
で、sibling が B:-1 に切り替わって 8a 通過なのか。こうなるのかな。
;; B:-1.5 => -1.5 ;; R:-1 => -1 ;; 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
で次に R:0.5 削除。末端の赤なのでそのまま削除。
;; B:-1.5 => -1.5 ;; R:-1 => -1 ;; B:-0.5 => -0.5 ;; B:0 => 0 ;; B:1 => 1 ;; B:2 => 2 ;; B:2.5 => 2.5 ;; B:3 => 3 ;; B:3.5 => 3.5 ;; R:4 => 4
昨晩もここまでは無事にナニできてます。次に B:1 が削除。sibling が赤ですね。あ、昨晩は最初の 8a なソレが間違っていたのか成程。まず以下な状態になって
;; B:-1.5 => -1.5 ;; B:-1 => -1 ;; B:-0.5 => -0.5 ;; R:0 => 0 ;; B:2 => 2
削除対象は右なのでコメントの通り 4b ですね。R:0 を基に rotate_right されます。こうなるのかな? sibling は B:-0.5 になるのかな。
;; B:-1.5 => -1.5 ;; B:-1 => -1 ;; B:-0.5 => -0.5 ;; R:0 => 0 ;; B:2 => 2
で、8b を通過してこうなるの?
;; B:-1.5 => -1.5 ;; B:-1 => -1 ;; R:-0.5 => -0.5 ;; B:0 => 0 ;; B:2 => 2
これ、平衡ではないな。リトライ。B:1 が削除される直前の部分木が以下。parent が B:0 で sibling が R:-1 になるのか。
;; B:-1.5 => -1.5 ;; R:-1 => -1 ;; B:-0.5 => -0.5 ;; B:0 => 0 ;; B:1 => 1 ;; B:2 => 2
parent を赤、sibling を黒にして
;; B:-1.5 => -1.5 ;; B:-1 => -1 ;; B:-0.5 => -0.5 ;; R:0 => 0 ;; B:2 => 2
R:0 を基に rotate_right します。
;; B:-1.5 => -1.5 ;; B:-1 => -1 ;; B:-0.5 => -0.5 ;; R:0 => 0 ;; B:2 => 2
これ、末端側が R だったら辻褄が合うんだけどなぁ。parent が R:0 のままで sibling が B:-0.5 になり、8b ってさっきと同じだなぁ。そもそも sibling が B:-0.5 だとして黒にならないといけない sibling->left が nil だなぁ。
おそらくは、なんですが赤黒木の特徴として
- 末端赤は許容
- 末端でない赤は両方子供が居ないとまずい
- しかも両方黒でないと駄目
なので
;; B:-1.5 => -1.5 ;; B:-1 => -1 ;; B:-0.5 => -0.5 ;; R:0 => 0 ;; B:2 => 2
ってなってれば平衡なんだけどこうならないのかどうなのか。んーと、R:0.5 削除が微妙なのかな。あ、5 を通過するのかな。違う。6 だ。
リトライ
- 2 と 0.5 を削除した直後の状態が以下。
;; B:-1.5 => -1.5 ;; R:-1 => -1 ;; B:-0.5 => -0.5 ;; B:0 => 0 ;; B:1 => 1 ;; B:2 => 2 ;; B:2.5 => 2.5 ;; B:3 => 3 ;; B:3.5 => 3.5 ;; R:4 => 4
ここで B:1 が削除なのですが 4b なケイスとして
;; B:-1.5 => -1.5 ;; B:-1 => -1 ;; B:-0.5 => -0.5 ;; R:0 => 0 ;; B:2 => 2
となった後に親が赤で sibling な B:-0.5 の子供が両方黒な 6 のケイスになるのか成程。以下になって終われば
;; B:-1.5 => -1.5 ;; B:-1 => -1 ;; R:-0.5 => -0.5 ;; B:0 => 0 ;; B:2 => 2
末端赤で平衡。やれやれ。この状態で B:2 が削除になる。これ、B:0 と swap して以下な状態になるのかな。
;; B:-1.5 => -1.5 ;; B:-1 => -1 ;; R:-0.5 => -0.5 ;; B:2 => 2 ;; B:0 => 0
で、B:2 が削除。parent は B:-1 で、sibling は B:-1.5 になるのかな。これ、子供が赤なパターンだな。こうなるの?
;; B:-1.5 => -1.5 ;; B:-1 => -1 ;; R:-0.5 => -0.5 ;; B:0 => 0
で、黒に変わって以下で終了なのか。
;; B:-1.5 => -1.5 ;; B:-1 => -1 ;; B:-0.5 => -0.5 ;; B:0 => 0
うーん、これって 3 なケイスを通過してないぞ。一応赤黒的には平衡ですが。これで -1 削除でどうなるんだろ。swap_node で以下になって
;; B:-1 => -1 ;; B:-1.5 => -1.5 ;; B:-0.5 => -0.5 ;; B:0 => 0
B:-1 が削除。parent は B:-1.5 ですね。これは 5 なケイスですね。sibling な色が赤になって繰り返し。
;; B:-1.5 => -1.5 ;; R:-0.5 => -0.5 ;; B:0 => 0
で、child が B:-1.5、parent が B:0 になって 3 を通過して終了なのか。すばら。
つーことで
再度纏めに着手したいと思ってるんですが、
/* At this point, child is BLACK. */
if (parent == NULL) { DELETE_CASE("3"); return; }な deletion case3 をパスさせるのにこんなに苦労するのか (絶句
