赤黒木 (3)
うーん、あまり仕様を理解していないのが敗因なのだろうか、と言いつつ wikipedia を確認するなど。二分探索木な仕様以外に以下を満足する必要あるらしい。
1.各ノードは赤か黒の色をもつ。
2.根は黒である。
3.葉はすべて黒である（したがって、赤のノードは子をもつ）。
4.赤のノードの子ノードはすべて黒である（したがって、対偶より、赤のノードの親ノードもすべて黒である）。
5.どのノードからも、子孫にあたる葉までの道に含まれる黒いノードの数は、一定である（この条件は、「根から葉までの道に含まれる黒いノードの数は、葉によらず一定である」と言い換えることができる）。
赤黒木 - wikipedia より引用
最初、赤と黒が順に出てくる? って思ってたのですがそうでもないらしい。どっちかというと上の 5. にある黒ノードの数が一定、てのが大事らしい。
ちょっと微妙なパターンを確認したので控えつつ再確認してみます。
gosh> (define tree (make-rbtree = <)) tree gosh> tree #<<rbtree> 0x1970c40> gosh> (rbtree-put! tree 3 "3") #<undef> gosh> (define (root-of-tree tree) (ref tree 'root)) root-of-tree gosh> (root-of-tree tree) #<<node> 0x19700f0> gosh> (ref (root-of-tree tree) 'key) 3 gosh> (ref (root-of-tree tree) 'color) black gosh> (ref (root-of-tree tree) 'left) #:nil-4 gosh> (ref (root-of-tree tree) 'right) #:nil-4 gosh>
一つ追加してみます。あと、手続き追加。
gosh> (rbtree-put! tree 6 "6") #<undef> gosh> (define (right-of-node node) (ref node 'right)) right-of-node gosh> (define (left-of-node node) (ref node 'left)) left-of-node gosh> (right-of-node (root-of-tree tree)) #<<node> 0x19761f0> gosh> (left-of-node (root-of-tree tree)) #:nil-4 gosh>
右に追加されてます。たぶん root が 3 で右に 6 が、という形で追加されてるはず。
gosh> (ref (root-of-tree tree) 'key) 3 gosh> (ref (root-of-tree tree) 'color) black gosh> (ref (right-of-node (root-of-tree tree)) 'key) 6 gosh> (ref (right-of-node (root-of-tree tree)) 'color) red gosh>
末端までの黒の数が云々、って意味では
black (3)
|
+----+----+
| |
black red (6)
|
+--+--+
| |
black blackということになるのか。次に 9 な要素を追加したらどうなるのか。
gosh> (rbtree-put! tree 9 "9") #<undef> gosh> (ref (root-of-tree tree) 'key) 6 gosh> (ref (root-of-tree tree) 'color) black gosh>
root は黒です。6 になってますね。左の要素を見てみます。
gosh> (ref (left-of-node (root-of-tree tree)) 'key) 3 gosh> (ref (left-of-node (root-of-tree tree)) 'color) red gosh>
左は赤ですね。つーことは右も赤なのかな。
gosh> (ref (right-of-node (root-of-tree tree)) 'key) 9 gosh> (ref (right-of-node (root-of-tree tree)) 'color) red gosh>
ここで 左の左に要素を追加したらどうなるのかな。
gosh> (rbtree-put! tree 1 "1") #<undef> gosh> (ref (left-of-node (root-of-tree tree)) 'key) 3 gosh> (ref (left-of-node (root-of-tree tree)) 'color) black gosh>
を、黒になった。その左は赤らしい。
gosh> (ref (left-of-node (left-of-node (root-of-tree tree))) 'key) 1 gosh> (ref (left-of-node (left-of-node (root-of-tree tree))) 'color) red gosh>
そして右側も黒になってますね。
gosh> (ref (right-of-node (root-of-tree tree)) 'key) 9 gosh> (ref (right-of-node (root-of-tree tree)) 'color) black gosh>
ええとイメージてきには以下?
black (6)
|
+--------+--------+
| |
black (3) black (9)
| |
+-----+-----+ +--+--+
| | | |
red (1) black black black
|
+--+--+
| |
black blackぬぬ、三つですね。つうことは red (1) の下に入るケイス以外は (black (3) とか black (9) の下に追加されるケイス) 赤なナニが、ということなのか。
put-fixup! 見てみるに追加された要素の親が黒だと何もしない形になってますね。とりあえずチェックする必要があるのは
- 1 な key が追加された時に put-fixup! でどんな操作がされているのか
- 0 とか 2 な key が追加される時に put-fixup! で何が起きてどうなるのか
というあたりか。
shiro さんからフォロー頂きました
曰く
refのネストは (〜 tree 'root 'left 'key) などと書くとすっきりしますよー。
とのこと。このあたりの確認含め、もうすこしもごもごしてみます。
追記
エントリ改めるの面倒なので。上のケイスですが 0 とか 2 な key を追加すると以下になるのかな。簡単な例、ってことで 2 を追加。
black (6)
|
+--------+--------+
| |
black (2) black (9)
| |
+-----+-----+ +--+--+
| | | |
red (1) red (3) black black
| |
+--+--+ +--+--+
| | | |
black black black black最初は 1 の下に入るのかと思ったんですが、black の個数てきに微妙。追加してみましょうね。
gosh> (rbtree-put! tree 2 "2") #<undef> gosh> (ref (left-of-node (left-of-node (root-of-tree tree))) 'key) 1 gosh> (ref (right-of-node (left-of-node (root-of-tree tree))) 'key) 3 gosh> (ref (left-of-node (root-of-tree tree)) 'key) 2 gosh>
色を確認してみます。
gosh> (ref (left-of-node (root-of-tree tree)) 'color) black gosh> (ref (left-of-node (left-of-node (root-of-tree tree))) 'color) red gosh> (ref (right-of-node (left-of-node (root-of-tree tree))) 'color) red gosh>
一応想定した通りになってる模様です。put-fixup! 確認しつつ検証してみます。追加直後 (put-fixup! 呼び出し直前) は red な key が 1 の右側に red な要素が追加されている形になっているはず、が前提で。
(let loop ((z z))
(when (red? (parent z))z の親は red です。
(let* ((b (eq? (parent z) (left (parent (parent z)))))
(y (right* (parent (parent z)) b)))b は真か。y には black (3) の右の要素なポインタが保存されるのか。
(if (red? y)
つーことは y は黒。
(let1 z (if (eq? z (right* (parent z) b))
(begin0 (parent z)
(left-rotate! tree (parent z) b))
z)z には次の式が戻す値がナニ。z の親の右は自分だな。なので z は z の親の red (1) が束縛されることになるのですが、その前に left-rotate! 手続きが呼び出されます。
うーん
やっぱ left-rotate! がアレ。でも left-rotate! は再起手続きではないのだな。これ、テスツをきちんと書けば理解がもう少し深まりそうな気がしてきています。や、今用意されてる試験が駄目って訳ではないです。
いちおう見てたケイスで left-rotate! が正常動作するはずなナニは確認できました。
試験か
とりあえず put-fixup! に渡す tree は適当で良いはず。で、z の上の上、な node までの範疇でオブジェクトができてれば良いはずなのでそのパターンを網羅できれば良いのかどうか。
あ、繰り返すパターンがあるな。ちょっと当分赤黒木を云々してやろうかな、と悪巧みしてたりなんかするんですがどうだろ (を
