赤黒木 (13)
朝の続きに着手。case 7a です。
最初の状態は以下な模様。
;; 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
直前の状態からここまでもってくる様子も確認してみたいですが、なんとなく赤赤になる (-0.5 を追加する時) ので回転して -1 が赤で追加、という形なのかどうか。
で、上記の状態から黒の -2 な node を削除するみたい。
;; 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.
削除後のイメージなコメントが無いですね。とりあえずおいかけてみます。つうかマンガ描いてみたらかなりバランス悪い木ですね。赤黒てきには平衡ですが。
まず以下。
(let1 z (if (and (not (nil? (left z))) (not (nil? (right z))))
(let1 y (successor z)
(set! (ref z 'key) (ref y 'key))
(set! (ref z 'value) (ref y 'value))
y)
z)z は末端 node ですので z はそのまま。
(let ((x (left* z (not (nil? (left z)))))
(p (parent z)))x は nil (x の右) で p は key が -1.5 の node になります。
(unless (nil? x)
(set! (parent x) p))スルー。
(if (nil? p)
(set! (root-of tree) x)
(set! (left* p (eq? z (left p))) x))p は nil ではないので z な node が切り離し。p の左要素は nil になります。
(when (black? z)
(delete-fixup! tree x p))z は黒なので delete-fixup! 手続きを呼び出します。x は nil で p は z の親の key が -1.5 の node になります。
(define (delete-fixup! tree x p)
(let loop ((x x) (p p))
(if (or (nil? p) (red? x))
(unless (nil? x)
(paint-black! x))p は nil ではなく、x は nil ですので、ここはスルー。
(let1 b (eq? x (left p))
(let1 w (let1 w (right* p b)
(if (red? w)
(begin (paint-black! w)
(paint-red! p)
(left-rotate! tree p b)
(right* p b))
w))p の左は nil なので b は #t ですね。で、w は p の右の key が -0.5 な要素を指します。ここは黒なので w はそのまんま。
(if (and (black? (left w)) (black? (right w)))
(begin (paint-red! w)
(loop p (parent p)))w の子供は片方赤なのでここもスルーですね。
(let1 w (if (black? (right* w b))
(begin (unless (nil? (left* w b))
(paint-black! (left* w b)))
(paint-red! w)
(right-rotate! tree w b)
(right* p b))
w)んーと、w の右は nil なので黒。ここ、初めて通過するパスかも。
- w の左 (key が -1) は nil ではないので黒になります (赤でした)
- w は赤になります
で、right-rotate! が呼び出されるのか。呼び出し直前の部分木が以下。
R:-1.5
B:-1
R:-0.5w は key が -1 な要素を指してます。よく見ると赤連続ですね。で、right-rotate! はトレイズ略で以下になります。
R:-1.5
B:-1
R:-0.5で、元に戻りますね。ええとこうなった結果、w は key が -1 な node を指す形になるのかな。で、以下。
(set! (ref w 'color)
(if (nil? p) 'black (ref p 'color)))
(paint-black! p)
(paint-black! (right* w b))あら、w の色が再度赤になり、親の色が黒になるのか。そして p の孫も黒になり、で以下?
B:-1.5
R:-1
B:-0.5で、
(left-rotate! tree p b)
が呼び出されます。ここも詳細スルーで以下になるのかな。
B:-1.5
R:-1
B:-0.5
B:0ありゃ、これで終わりそうだな。以下な状態になるのかどうか。
;; 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
一応平衡に見えますね。大丈夫かな。
これ
ddd みたくリンクと要素が見えるカンジな UI があってステップ実行できたら面白いのに、と思ってしまいました。
ちなみに
上記から 0.5 な node を削除するのが次の試験らしいんですが、赤なのでもう少しおいかけてみます。
# 実は止めようと思ってた (を
delete-node! 手続き先頭から確認。
(let1 z (if (and (not (nil? (left z))) (not (nil? (right z))))
(let1 y (successor z)
(set! (ref z 'key) (ref y 'key))
(set! (ref z 'value) (ref y 'value))
y)
z)ええと、末端要素なので z はそのまんま。
(let ((x (left* z (not (nil? (left z)))))
(p (parent z)))z は末端要素なので x は nil、p は key が 1 の node になります。
(unless (nil? x)
(set! (parent x) p))スルー。
(if (nil? p)
(set! (root-of tree) x)
(set! (left* p (eq? z (left p))) x))p から z へのリンクが切れます。
(when (black? z)
(delete-fixup! tree x p))z は赤なのでスルー。
(set! (left z) #f)
(set! (right z) #f)
(set! (parent z) #f))))後は z のリンクを切る処理。ということで以下になるのでしょうか。イメージ無いので超不安。
;; 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
平衡になっている、はず。。
で、次に 2 と -1 が削除される模様。残りが 4 つある模様。色々とへろへろなので今日は早めにクタバります。
