赤黒木 (4)
left-rotate! 手続きを確認。つうかその前に put-fixup! も要確認か。
まず put-fixup! をちょっとだけ。手続き定義を確認しつつメモを取ってみます。
(define (put-fixup! tree z)
(let loop ((z z))
(when (red? (parent z))繰り返しがあり得る、ということと繰り返しのその時点での処理対象である z の親要素が赤か、を確認しています。ちなみに手続きに渡される z は追加された要素になります。つうことは追加時に親要素が黒ならローテーションはやらないんですね。
で、次です。
(let* ((b (eq? (parent z) (left (parent (parent z)))))
(y (right* (parent (parent z)) b)))b の意味としては z の親要素はそのまた親の要素の左側の要素なのかどうか、ということになるはず。ということは y は z の親のもう片側の要素を指す形になるのか。
ちなみに put-fixup! 手続きではここで設定される b をそこら中で多用してます。ちなみに次に確認するブロックでは b は一切使われていないですね。
(if (red? y)
(begin
(paint-black! (parent z))
(unless (nil? y) (paint-black! y))
(paint-red! (parent (parent z)))
(loop (parent (parent z))))z の親の逆側の要素が赤だった場合、という意味になるのか。その場合
- z の親は黒にする
- z の親の逆側の要素が nil でなければここも黒にする
- z の親のそのまた親の要素は赤にする
- z の親のそのまた親を渡して loop に jmp する
- loop に渡されるのは「赤になった要素」なんスね。
ということは
black
|
+------+------+
| |
red red
| |
+---+---+ +---+---+
| | | |
black black black blackみたいな木の末端に要素が追加されたら
black
|
+------+------+
| |
red red
| |
+---+---+ +---+---+
| | | |
black black black red <- 追加
|
+---+---+
| |
black blackこうなるのか。
black
|
+------+------+
| |
black black
| |
+---+---+ +---+---+
| | | |
black black black red <- 追加
|
+---+---+
| |
black blackなるほど。つうか、別途試験で確認必要ですね。
次が微妙に難解な y (z の親の逆側の要素) が赤でなかった場合のブロックになります。
(let1 z (if (eq? z (right* (parent z) b))
(begin0 (parent z)
(left-rotate! tree (parent z) b))
z)
(paint-black! (parent z))
(paint-red! (parent (parent z)))
(right-rotate! tree (parent (parent z)) b))))))追加する要素は基本赤なんですが、その親が赤でかつその逆側も赤なら繰り返しになるのか。つうことはこのブロックに入ってくるケイスというのは
- 追加要素赤
- その親が赤
- 追加要素の親の逆側にいる要素は赤ではない
ということか。ちなみに繰り返しが発生するケイスを想定してみました。
+-黒
|
+-黒-+
| |
| +-黒
+-赤-+
| | +-黒
| | |
| +-黒-+
| |
| +-黒
黒-+ +-黒
| +-赤-+
| | +-黒
| +-黒-+
| | |
| | +-黒
+-赤-+ +-黒 <- ここに新たに赤追加
| +-赤-+
| | +-黒
+-黒-+
| +-黒
+-赤-+
+-黒すると一回目で以下になって
+-黒
|
+-黒-+
| |
| +-黒
+-赤-+
| | +-黒
| | |
| +-黒-+
| |
| +-黒
黒-+ +-黒
| +-赤-+
| | +-黒
| +-黒-+
| | |
| | +-黒 +-黒
+-赤-+ +-赤-+
| +-黒-+ +-黒
| | +-黒
+-赤-+
| +-黒
+-黒-+
+-黒もっかい繰り返して以下になる、と。
+-黒
|
+-黒-+
| |
| +-黒
+-黒-+
| | +-黒
| | |
| +-黒-+
| |
| +-黒
黒-+ +-黒
| +-赤-+
| | +-黒
| +-黒-+
| | |
| | +-黒 +-黒
+-黒-+ +-赤-+
| +-黒-+ +-黒
| | +-黒
+-赤-+
| +-黒
+-黒-+
+-黒末端黒まで 4 step で統一されてますね。話を元に戻すと親の逆側の要素が黒のケイスというのは例えば以下。
+-黒 <- ここに新規追加 +-赤-+ 黒-+ +-黒 +-黒
追加するとこうなります。
+-黒
+-赤-+
+-赤-+ +-黒
黒-+ +-黒
+-黒そうか親が赤で対面が黒ってのは nil 確定ってことで良いのかな。あ、さっきの例だとそうでもないですね。や、親が赤でその対面が黒、ってのはやはりアンバランスなケイスに限定できるか。
とすると上のソレを含めてパターン的には以下なのかどうか。
+-黒
+-赤-+ +-黒
黒-+ +-赤-+
+-黒 +-黒
+-黒 +-黒
黒-+ +-赤-+
+-赤-+ +-黒
+-黒
+-黒
黒-+ +-黒
+-赤-+ +-黒
+-赤-+
+-黒b が真になるのは 3 番目と 4 番目か。あるいは
(let1 z (if (eq? z (right* (parent z) b))
の if なソレが真になるのは 3 番目および 2 番目で良いのかな。親がいる場所と逆に位置に居る、という表現で良いのかどうか。とりあえず上四つについて机上で展開してみれば良いですね。
展開してみた
2 および 3 については let1 の中の left-rotate! で 1 とか 4 な形に整形されてますね。で、いっちゃん下の right-rotate! で 1 とか 4 な形のソレをバランスが取れた状態にしている模様。
とりあえず 3 のケイスから確認してみます。
+-nil(4) +-nil(3)
黒-+ +-赤-+
+-赤-+ +-nil(2)
+-nil(1)nil 要素に番号ついてますが特に深い意味はありません。条件てきにこれは left-rotate! を実行するパターンになります。あ、あと b は true です。追加する要素の親はその親の左側の要素になってます。
(let1 z (if (eq? z (right* (parent z) b))
(begin0 (parent z)
(left-rotate! tree (parent z) b))
z)z を親要素に設定しなおしてますが left-rotate! の後の状態を見越した処理です。
で、left-rotate! の定義ですが以下です。
(define (left-rotate! tree x b)
(let1 y (right* x b) ;; 0.
(set! (right* x b) (left* y b)) ;; 1.
(unless (nil? (left* y b))
(set! (parent (left* y b)) x))
(set! (parent y) (parent x)) ;; 2.
(cond ((nil? (parent x)) ;; 3.1
(set! (root-of tree) y))
((eq? x (left* (parent x) b)) ;; 3.2
(set! (left* (parent x) b) y))
(else ;; 3.3
(set! (right* (parent x) b) y)))
(set! (left* y b) x) ;; 4.
(set! (parent x) y))) ;; 5.順にメモを。x として渡されるのは追加された要素の親です。そして let1 で y にセットされるのは追加された要素になります。で、let1 の中身を順にたどります。
- x の右に y の左がセット
- x が指す要素は y の左要素になります
- y の左が nil でないなら y の左の要素の親は x にする
- 1. および 2. で y の左と x のリンクを貼り直しているのがわかります
- x の親要素に関する処理
- x の親が nil (root 要素) なら y を root にする
- x はその親の左側の要素であれば y を x の親の左側の要素に
- それ以外 (x はその親の右側の要素) は y を x の親の右側の要素に
- y の左要素を x にする
- x の親は y に
これで以下なイメージになります。
+-nil(4)
黒-+ +-nil(3)
+-赤-+ +-nil(2)
+-赤-+
+-nil(1)で、一番下の要素を x が指してる形になってます。この状態で要素の色を変えてます。
(paint-black! (parent z))
(paint-red! (parent (parent z)))こうなります。
+-nil(4)
赤-+ +-nil(3)
+-黒-+ +-nil(2)
+-赤-+
+-nil(1)で、right-lotate! を呼び出します。
(right-rotate! tree (parent (parent z)) b))))))
right-rotate! は b を逆にして left-rotate! を呼び出します。
(define (right-rotate! tree x b) (left-rotate! tree x (not b)))
ので、b が false の状態で x は一番下の赤い要素を指してる状態で呼び出されます。b が false なので right* とか left* とかは逆を取るカンジになります。このあたりの抽象化もすばら。
で、上の木について順に命令を適用していきます。y は黒い二番目の要素を指してる状態で開始されます。
- x の左に y の右をセット
- y の右が nil でないなら y の右の親は x
- x の親は nil なので (root 要素) y を root にする
- y の右要素に x を設定
- x の親は y に設定
これで以下な形に整形されます。
+-nil(4)
+-赤-+
| +-nil(3)
黒+
| +-nil(2)
+-赤-+
+-nil(1)一応 2 のケイスも確認しておきます。最初のイメージは以下。
+-nil(4) +-赤-+ +-nil(3) 黒-+ +-赤-+ +-nil(1) +-nil(2)
b は false です。追加要素の親はその親の右側の要素になっています。追加要素はその親から見て左側になるので begin0 なブロックを評価しにいきます。
(let1 z (if (eq? z (right* (parent z) b))
(begin0 (parent z)
(left-rotate! tree (parent z) b))で、left-rotate! です。
- x の左に y の右をセット
- y の右が nil でないなら y の右の親は x
- x は親の右側の要素なので y を x の親の右側の要素に
- y の右要素に x を設定
- x の親は y に設定
このソレを経て以下なイメージになります。
+-nil(4)
+-赤-+
+-赤-+ +-nil(3)
黒-+ +-nil(2)
+-nil(1) z は上イメージで言うといっちゃん末端要素を指してる形で色を変えます。
(paint-black! (parent z))
(paint-red! (parent (parent z)))以下になるのか。
+-nil(4)
+-赤-+
+-黒-+ +-nil(3)
赤-+ +-nil(2)
+-nil(1) で、right-rotate! を評価します。こんどは b は true な状態となります。
- x の右に y の左がセット
- y の左が nil でないなら y の左の要素の親は x にする
- x の親が nil (root 要素) なら y を root にする
- y の左要素を x にする
- x の親は y に
これでどうなるか、というとイメージ的には同じか。
+-nil(4)
+-赤-+
| +-nil(3)
黒+
| +-nil(2)
+-赤-+
+-nil(1)rbtree-put! というか put-fixup! と left-rotate! (right-rotate!) 凄い。
つうかここで確認できたソレを試験しなきゃ、なのか。
