赤黒木 (28)

現実トウヒな成果物としてのエントリです。何故か

  ;;        B:-3 => -3
  ;;      B:-2 => -2
  ;;        B:-1.5 => -1.5
  ;;    B:0 => 0

みたいな部分木ができる条件って何なのか、と思いたち case5 の試験の準備なソレを追い掛けてみました。とりあえず最初の状態が以下で

  ;;        B:-3 => -3
  ;;      R:-2 => -2
  ;;        B:-1.5 => -1.5
  ;;    B:0 => 0
  ;;      B:3 => 3

ここから順に 2 1 .5 2.5 3.5 4 と追加。
まず 2 が追加でこうなる。

  ;;        B:-3 => -3
  ;;      R:-2 => -2
  ;;        B:-1.5 => -1.5
  ;;    B:0 => 0
  ;;        R:2
  ;;      B:3 => 3

次に 1 追加。

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

これは回転して整形するパターン。

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

次 0.5 追加。部分木で以下。

  ;;    B:0 => 0
  ;;          R:0.5
  ;;        R:1
  ;;      B:2
  ;;        R:3 => 3

あ、ここで繰り返しになるのか。こうなって繰り返し。

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

で、R:2 がカレントな要素になって云々。でも親が黒だからこれで終わりなのか。次はここに 2.5 な要素が追加されます。

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

そして 3.5 が追加。これ、なんとなく繰り返しが続きそげに見えます。

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

で、最後に 4 が追加。

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

これ、繰り返しなパターンですね。以下になって

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

R:3 が追加された扱いでこうなるのか。

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

で、てっぺんが黒になって終了か。うーん。

もう少し

ちなみに削除時の整形では

  ;;        B:-3 => -3
  ;;      R:-2 => -2
  ;;        B:-1.5 => -1.5

で追加時の整形では

  ;;        R:-3 => -3
  ;;      B:-2 => -2
  ;;        R:-1.5 => -1.5

にしているのも何か理由があるのだろうな。つうかおそらく削除後になされる整形な部分木が追加処理の繰り返しな 3 のケイスで色が変えられるパターンで

  ;;        B:-3 => -3
  ;;      B:-2 => -2
  ;;        B:-1.5 => -1.5

な部分木はできるのだろう。ということはこの部分木の親は黒限定になるのかどうか。