赤黒木 (25)

gauche

なかなかにハードル高いです。ちなみに会議中の現実トウヒな成果。

ある削除のパターン

4a とか 4b などの削除対象 node の sibling が赤、というケイス。一般的 (?) には以下のような部分木の B:2 な要素を削除するようなケイスになります。

  B:2
B:3
    B:4
  R:5
    B:6

親を赤くして sibling を黒にして

R:3
    B:4
  B:5
    B:6

回転。

  R:3
    B:4
B:5
  B:6

parent は R:3 で sibling は B:4 です。以下にして終了、なのか。

  B:3
    R:4
B:5
  B:6

ちなみに

sibling が赤 node ということなんですが赤 node は子供が居ないか黒い子供が両方居るか、というどちらかのケイスしか無いはず、ということで

  B:2
B:3
  R:5

こんなのがあり得るか、というと無いですね。ので、4[ab] なパターンは

  B:2
B:3
    B:4
  R:5
    B:6

とか

    B:2
  R:3
    B:4
B:5
  B:6

から B:6 削除するようなケイスに限定できるのかどうか。そうだとすると 4[ab] は 6 と通って終わる、と限定できるんだけどな。

6 なケイスのみを通過するソレ

以下な部分木からどちらかの末端を削除するケイス。

  B:2
R:3
  B:4

例えば B:2 が削除とすると以下で終わる模様。

B:3
  R:4

赤黒的には平衡。6 のみ通過するのはこのケイス限定?

む

7* から 8* というソレは例えば末端部分木の

  B:0
    R:2
R:5
  B:6

から B:6 を削除した時、残りの曲った部分木をまっすぐにして折り畳むような処理をしています。まず、こうなって

    R:0
  B:2
R:5

これを折り畳む形になります。

    R:0
  B:2
R:5

折り畳むと以下か。

  B:0
R:2
  B:5

逆に整形しなくて良い形であれば 8* のみ、で、という事なのか。

纏めてみる

  • 7* および 8* は部分木の整形な後処理
  • 5 としては黒が濃い場合の間引きとしての
  • 6 の意味としては削除された node の親が赤で、sibling な要素の子供が無いケイス
  • 4 はイメージ的に sibling が赤だと向こうの方が深い、と見て良いのかな
    • これ、追加のケイスもこうした判断で云々なのか

6 な例だと

  B:4
R:5
  B:3

の R:5 を削除するケイスだと 6 に合致するのか。ぬ、4 から 5 に移行して繰り返すパターンがあるかと思ったんですが 4* で parent の色が赤になりますね。

追加について

追加時、親が赤 node で

  • sibling が赤なら繰り返し
  • そうでなければ云々
    • 基本的には sibling が nil って理解で良いのかどうか

このあたりまで

頭のなかで整理できたら Scheme な手続きも理解しやすくなってるのかどうか。つうか整理できてるのかそうでもないのかが微妙です。
あとは shiro さんが作成なさった試験を掘削 (?) して終わる方向。