赤黒木 (29)

gauche

そろそろ終わりも近いがどうなるか。
とゆーことで削除の試験の確認ですが継続は deletion case7a からのはず、ということで確認します。
最初の状態は以下とのこと。

  ;;          B:-2 => -2
  ;;        R:-1.5 => -1.5
  ;;            R:-1 => -1
  ;;          B:-0.5 => -0.5
  ;;      B:0 => 0
  ;;          R:0.5 => 0.5
  ;;        B:1 => 1
  ;;    B:2 => 2
  ;;        B:2.5 => 2.5
  ;;      B:3 => 3
  ;;        B:3.5 => 3.5
  ;;          R:4 => 4

ここから B:-2 な要素を削除。4、5、6 はスルーで 7a ですね。色が変えられて

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

sibling を基点に回転。

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

で、sibling は B:-1 ということにしといて削除時の最終整形ですね。

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

大丈夫かな。全体で見てみると以下。

  ;;          B:-1.5 => -1.5
  ;;        R:-1 => -1
  ;;          B:-0.5 => -0.5
  ;;      B:0 => 0
  ;;          R:0.5 => 0.5
  ;;        B:1 => 1
  ;;    B:2 => 2
  ;;        B:2.5 => 2.5
  ;;      B:3 => 3
  ;;        B:3.5 => 3.5
  ;;          R:4 => 4

平衡になってますね。次は deletion case4b ということで 0.5 と 1 が順に削除される模様。0.5 は赤い末端 node なのでそのまま削除で、1 の sibling は赤になっているので 4 なんですね。削除 node が右側なので 4b になるのか。
右側に回転させて整形というカンジなのかどうか。回転前の状態が以下で

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

parent を基点に右回転なのでこうなるのかな?

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

これは右側の部分木を一直線にして云々? ちなみにこの時点で parent は R:0 で sibling は B:-0.5 に変更されるはず。これは deletion case6 ということで以下になって終了なのか。

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

全体としては以下?

  ;;        B:-1.5 => -1.5
  ;;      B:-1 => -1
  ;;          R:-0.5 => -0.5
  ;;        B:0 => 0
  ;;    B:2 => 2
  ;;        B:2.5 => 2.5
  ;;      B:3 => 3
  ;;        B:3.5 => 3.5
  ;;          R:4 => 4

なんというか黒が濃ゆい赤黒木だなぁ。そしてここから 2 および -1 を削除して deletion case3 を云々とあります。B:0 と交換で削除なのかな。

  ;;        B:-1.5 => -1.5
  ;;      B:-1 => -1
  ;;          R:-0.5 => -0.5
  ;;        B:2 => 2
  ;;    B:0 => 0

色が同じで良かった (何
parent は B:-1 で sibling が B:-1.5 で child は R:-0.5 です。これは繰返しのパターンですね。以下になって

  ;;        R:-1.5 => -1.5
  ;;      B:-1 => -1
  ;;        R:-0.5 => -0.5
  ;;    B:0 => 0
  ;;        B:2.5 => 2.5
  ;;      B:3 => 3
  ;;        B:3.5 => 3.5
  ;;          R:4 => 4

B:-1 が child で B:0 が parent になるのか。sibling は B:3 ですね。再び繰返しのパターンとなり、parent が NULL になって終了。て、これ平衡になってないぞ。あ、繰返しの時に sibling なソレが赤になるから最終状態はこうか。

  ;;        R:-1.5 => -1.5
  ;;      B:-1 => -1
  ;;        R:-0.5 => -0.5
  ;;    B:0 => 0
  ;;        B:2.5 => 2.5
  ;;      R:3 => 3
  ;;        B:3.5 => 3.5
  ;;          R:4 => 4

これなら辻褄が合いますね。ここからさらに -1 が削除。これはリンク貼り替えられるけど色はそのままになる swap_node のソレで以下な状態になります。

  ;;        R:-1 => -1
  ;;      B:-1.5 => -1.5
  ;;        R:-0.5 => -0.5

で、末端赤 node の削除なのでこうなる、と。

  ;;      B:-1.5 => -1.5
  ;;        R:-0.5 => -0.5
  ;;    B:0 => 0
  ;;        B:2.5 => 2.5
  ;;      R:3 => 3
  ;;        B:3.5 => 3.5
  ;;          R:4 => 4

残った試験は deletion case4a な模様。以下な状態から

  ;;      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 を削除な模様。parent は B:-1 で sibling が R:-0.6 になります。削除対象は左側なので 4a なのか。以下な状態から

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

R:-1 を基点に左回転。こうなるのかな。。

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

sibling は B:-0.7 に変更されるはず。6 を通過して終了パターンなのか。

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

そして

これからパスを検証してみます。