赤黒木 (5)
現実トウヒなメモです。直前エントリも同様ですが (を
wikipedia に出ているサンプルが以下なんですが
+- nil
+- 赤 (27) -+
| +- nil
+- 黒 (25) -+
| | +- nil
| +- 赤 (22) -+
+- 赤 (17) -+ +- nil
| | +- nil
| +- 黒 (15) -+
| +- nil
黒 (13) -+
| +- nil
| +- 黒 (11) -+
| | +- nil
| | +- nil
+- 赤 (8) -+ +- 赤 (6) -+
+- 黒 (1) -+ +- nil
+- nilこいつに要素を追加するとどうなるか、ってソレです。ちなみに
- 黒 (1)
- 黒 (11)
- 黒 (15)
の下に要素を追加する場合は回転が発生しないですよね。逆に回転させないといかんのは
- 赤 (6)
- 赤 (22)
- 赤 (27)
の下に要素が追加される場合になります。値としては例えば 5 とか 7 とか 20 とか 24 とか 26 とか 28 とか。あ、でも
- 5
- 24
- 26
は left-rotate! が先に動いて云々だけど右側の部分木は left-rotate! ふくめてトレイスしてみると面白そうですね。左側の 5 とか 7 とかは単純な例なのでスルーします。
20 を追加してみる
む、これって繰り返しなパターンになるんですね。回転しないのか。最初は一部のみで。
+- nil
+- 赤 (27) -+
| +- nil
+- 黒 (25) -+
| | +- nil
| +- 赤 (22) -+ +- nil
+- 赤 (17) -+ +- 赤 (20) -+
| | +- nilput-fixup! に入って b は真で y は赤 (27) を指してる状態になるのかな。y が赤なので以下なブロックに入ると。
(if (red? y)
(begin
(paint-black! (parent z))
(unless (nil? y) (paint-black! y))
(paint-red! (parent (parent z)))
(loop (parent (parent z))))ええと以下な状態になって
+- nil
+- 黒 (27) -+
| +- nil
+- 赤 (25) -+
| | +- nil
| +- 黒 (22) -+ +- nil
+- 赤 (17) -+ +- 赤 (20) -+
| | +- nilで、赤になった (25) が loop に渡されます。全体てきには以下な状態です。
+- nil
+- 黒 (27) -+
| +- nil
+- 赤 (25) -+
| | +- nil
| +- 黒 (22) -+ +- nil
+- 赤 (17) -+ +- 赤 (20) -+
| | +- nil
| | +- nil
| +- 黒 (15) -+
| +- nil
黒 (13) -+
| +- nil
| +- 黒 (11) -+
| | +- nil
| | +- nil
+- 赤 (8) -+ +- 赤 (6) -+
+- 黒 (1) -+ +- nil
+- nilええと、b は偽で y は赤 (8) か。再び y が赤なので以下になりますか。
+- nil
+- 黒 (27) -+
| +- nil
+- 赤 (25) -+
| | +- nil
| +- 黒 (22) -+ +- nil
+- 黒 (17) -+ +- 赤 (20) -+
| | +- nil
| | +- nil
| +- 黒 (15) -+
| +- nil
赤 (13) -+
| +- nil
| +- 黒 (11) -+
| | +- nil
| | +- nil
+- 黒 (8) -+ +- 赤 (6) -+
+- 黒 (1) -+ +- nil
+- nilで、赤 (13) が loop に渡されるんですが、親が居ないので赤 (13) が黒になって終了となります。末端まで 4 つ黒という形で平らになってますね。
24 追加
こうなるのかな。
+- nil
+- 赤 (27) -+
| +- nil
+- 黒 (25) -+ +- nil
| | +- 赤 (24) -+
| +- 赤 (22) -+ +- nil
+- 赤 (17) -+ +- nilこれも親の対面が赤なのでアレ。これって 26 とか 28 とか全部同じですね。どっちかというと 20 を追加した後、さらに 19 とかを追加してみるとかの方が面白そうかも。
+- nil
+- 黒 (27) -+
| +- nil
+- 赤 (25) -+
| | +- nil
| +- 黒 (22) -+ +- nil
+- 黒 (17) -+ +- 赤 (20) -+ +- nil
| | +- 赤 (19) -+
| | +- nil +- nil
| +- 黒 (15) -+
| +- nilあら、でもこれって
+- nil
+- 黒 (27) -+
| +- nil
+- 赤 (25) -+ +- nil
| | +- 赤 (22) -+
| | | +- nil
| +- 黒 (20) -+
| | +- nil
+- 黒 (17) -+ +- 赤 (19) -+
| | +- nil
| | +- nil
| +- 黒 (15) -+
| +- nilこうなって終了しそう。むむ。left-rotate! の以下な unless の中身が実行されるケイスが分からない。
(define (left-rotate! tree x b)
(let1 y (right* x b)
(set! (right* x b) (left* y b))
(unless (nil? (left* y b))
(set! (parent (left* y b)) x))バランスが悪いケイスで出るのだろうか。
つーことで
現実トウヒは一旦仕舞います。試験書きたひ (を
