赤黒木 (24)

gauche

纏めに三度着手。の前に赤い要素の仕様を。

  • 末端赤は許容
  • 末端でない赤は左右両方に黒の要素を持つ

という理解だけど良いのかどうか。

とりあえず

case4 以降の条件を整理してみます。case2 以降は削除対象要素は黒限定となります。

  • case4 は削除対象の要素の sibling な要素が赤
  • case5 は親が黒で削除対象要素の sibling の子供が両方黒
    • At this point, sibling is BLACK というコメントがある件
  • case6 は親が赤で削除対象要素の sibling の子供が両方黒
  • case7a は削除対象要素がその親の左側の子供でその sibling な要素の子供の左側が赤で右側が黒
  • case7b は削除対象要素がその親の右側の子供でその sibling な要素の子供の左側が黒で右側が赤
  • case8 は case4 および case7 の場合実行される後処理

これ的情報は昨晩エントリにもありますね。

むむむ

駄目だ。追いかけてた中で分かったことを列挙してみると

  • case4 あるいは case7 の後、sibling の削除対象の逆側の子供は存在している
    • もしかしたら赤かも

試験から確認してみます。4a の試験で最初の状態が以下。

  ;;      B:-2 => -2
  ;;    B:-1 => -1
  ;;        B:-0.7 => -0.7
  ;;      R:-0.6 => -0.6
  ;;          R:-0.5 => -0.5
  ;;        B:0 => 0

ここから B:-2 な要素を削除。親 (B:-1) を赤にして sibling なソレ (R:-0.6) を黒に。

  ;;    R:-1 => -1
  ;;        B:-0.7 => -0.7
  ;;      B:-0.6 => -0.6
  ;;          R:-0.5 => -0.5
  ;;        B:0 => 0

で、親を基点に rotate_left して以下?

  ;;      R:-1 => -1
  ;;        B:-0.7 => -0.7
  ;;    B:-0.6 => -0.6
  ;;        R:-0.5 => -0.5
  ;;      B:0 => 0

あ、ここで 6 のケイスと評価されるのか。必ず 8 って訳ではないのね。ここから R:-1 が黒になって B:-0.7 が赤になって以下。

  ;;      B:-1 => -1
  ;;        R:-0.7 => -0.7
  ;;    B:-0.6 => -0.6
  ;;        R:-0.5 => -0.5
  ;;      B:0 => 0

必ず 4* から 8 という訳ではないのか。この場合、6 を通って終わってますね。むむむむ的。あら、昨晩の 4b なケイスも 6 になって終了してますね。7* は必ず 8 を通過するのは当り前なんですが、4* からは必ず、という訳ではないのか。
む、6 を通過するのは slibing の子供が両方黒というケイスなのか。うーん、やはりこのあたりの条件を色々確認しないとアレですね。

それぞれのケイスが

実行される条件とその結果を纏めないとアレ。つうかその前に赤い node の仕様を列挙しましたが黒い node の仕様は以下になるのかな。

  • 黒 node は子供を持たない場合がある (これは赤 node も同様)
  • 黒 node は赤い子供 node を片方のみ持つ場合がある
  • 黒 node は黒い子供 node を片方のみ持つことは無い
  • 黒 node は左右に子供を持つ場合、全ての組み合せの可能性があり得る
    • 赤-赤、黒-赤、赤-黒、黒-黒
  • sibling な node についても nil を含めて全ての可能性があり得る

うーん。1 から順にいくつか追加してみて確認してみます。まず空の木に R:1 を追加したら以下に。

B:1

次に 2 な要素追加。

B:1
  R:2

次に 3 な要素追加。

B:1
  R:2
    R:3

親が赤。親はその親の右側の要素。親の sibling は nil です。あら? 右に回転しとるな、と思ったら b は #f だった。こうなるのか。

  R:1
B:2
  R:3

次に 4 が追加。

  R:1
B:2
  R:3
    R:4

同じカンジかな。ただ、親の sibling は nil ではないですね。あ、赤なので繰り返すのかな。R:3 を黒にして R:1 も黒にして B:2 を赤にして

  B:1
R:2
  B:3
    R:4

R:2 が z に渡されて繰り返し。最後に R:2 が黒になって終了か。

  B:1
B:2
  B:3
    R:4

次に R:5 を追加。

  B:1
B:2
  B:3
    R:4
      R:5

今度は親の sibling は nil か。こうなって

  B:1
B:2
  R:3
    B:4
      R:5

R:3 基点で左回転。

  B:1
B:2
    R:3
  B:4
    R:5

追加は基本、一直線にして上の状態にするのが基本なのかな。あとは B:4 先頭な部分木について R:4 追加したときと同じ形になるはず。

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

ええと、親を黒にして、親の sibling も黒にして B:4 は赤にして繰り返し。

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

を、でもこんどは二回繰り返しが続くな。でも親が黒なのでこれで終わりなのか。ちなみにこの状態で R:5.5 を追加すると

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

ここから一直線に修正して

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

こうなります。

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

そろそろ root が変わらんかな。

  B:1
B:2
    B:3
  R:4
      R:5
    B:5.5
      R:6
        R:7

親が赤、親の sibling も赤。こうなって

  B:1
B:2
    B:3
  R:4
      B:5
    R:5.5
      B:6
        R:7

繰返し。R:5.5 が z になるのか。親も赤。親の sibling は黒。親を黒にして親の親を赤にして root な要素を基点に左回転。

  B:1
R:2
    B:3
  B:4
      B:5
    R:5.5
      B:6
        R:7

こうなるのか。

    B:1
  R:2
    B:3
B:4
    B:5
  R:5.5
    B:6
      R:7

もっかい確認

ええと R:6 を追加した後の状態が以下なんですが

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

ここに B:5.5 な部分木について要素を追加したらバランスが崩れるので root が変更になるほどの回転が発生するはず。ちなみに繰り返しが発生する条件としては追加する要素の親の sibling が赤だった場合。この状態ですね。

      R:5
    B:5.5
      R:6

こうなってたら全部色を切り換えて、てことか。ここに例えば 7 を追加するケイスだと単純に回転するのみか。

    B:5.5
      R:6

で、例えば B:1 とか B:3 な部分木に要素が追加される場合はそのまま、なのか。

これを踏まえて

削除なナニを確認してみたいんですが今日は限界かなぁ。む、基本的にこんなケイスはあり得ない、のかな。。

  ;;        R:-1 => -1
  ;;      B:0 => 0
  ;;        B:1 => 1

部分木としてあり得るパターンというのは確認してみる必要があるのかどうか。あるいはそんなに単純な話になるのかどうなのか。