赤黒木 (32)

gauche

小さい部分木で考えてみると良いのかどうなのか、と言いつつ確認してみました。
ええとまず、片方だけ子供が居る部分木は親の色が黒限定で子供は赤限定。

  R:-2
B:-1

とか

B:-1
  R:0

とか。逆に両方子供が居る、というケイスについては親は赤も黒もあり得ますし、子供も赤黒両方あり得るんですが、子供に子供が居ない場合は基本どちらも同じ色になるはず。
こんなのとか

  B:-2
B:-1
  B:0

こんなのとか

  B:-2
R:-1
  B:0

こんなのとか

  R:-2
B:-1
  R:0

それぞれ末端 (というか子供) を削除したらどうなるか、というと最初のは

  B:-2
B:-1
  B:0

繰り返しになります (パタン 5)。こうなって削除な n の親と子が更新されて繰り返し。

  R:-2
B:-1

あるいは次のだと

  B:-2
R:-1
  B:0

こうなるのか (パタン 6)。

B:-1
  R:0

で、最後のこれは

  R:-2
B:-1
  R:0

色の変更はありません (パタン 1)。

B:-1
  R:0

あるいは親の要素が削除されたらどうなるのか、というと

  B:-2
B:-1
  B:0

これは繰り返しのパターンですね。-1 が削除される場合はこうなるので

  B:-1
B:-2
  B:0

結局パタン的に 5 になってしまうのか。あるいは以下だと

  B:-2
R:-1
  B:0

こうなって

  B:-1
R:-2
  B:0

こうなるのか

B:-2
  R:0

あるいは以下だと

  R:-2
B:-1
  R:0

こうなってスルーかな。

  R:-1
B:-2
  R:0

交換するけど色は変わらない、というあたりがアレ。

B:-2
  R:0

あとは三世代な部分木なんですが基本的な形として

  B: <- delete
?:
  B:
    R:

あるいは

  B: <- delete
?:
    R:
  B:

あるいは

  B: <- delete
?:
    R:
  B:
    R:

みたいな形になるのかどうか。ちなみに左側の部分木には片側のみ子供が、というケイスはありだと思ってます (削除対象は左側部分木の黒い要素)。逆のパターンは略してます。sibling 黒でその子供が両方黒ではないので 5 のパタンには合致しません。あ、親が赤だとしても 6 にも合致しないですね。

4[ab]

あり得そうなのは以下な形か。

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

ここから -2 な要素を削除すると相当バランスが崩れるのが分かります。削除対象の要素の sibling が赤の場合には二回転させないと、ということになるのかどうか。一つめの回転でこうなって

  R:0
    B:1
B:3
  B:4
    R:5

これは 6 なパタンに合致するのでこうなって終わるのか。

  B:0
    R:1
B:3
  B:4
    R:5

二回とか三回とか回転するケイスは繰り返しでないと発生しないのだろうか。あ、B:1 の要素に赤い子供がいるとどうなるかな。

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

ええと、-2 な要素が削除されて一回目の回転でこう

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

これは 6 なパタンに合致しないので 8a なパタンでこうなるのか。

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

まとめ

二世代な部分木であり得るケイスから見てみるに、4[ab] 以外のパタンは三世代な部分木で考えることができますね。ただし、4[ab] については実際にあり得る部分木としては四世代なソレになるのかどうか。ただ

  B:
B:
    B:
  R:
    B:

というのはあり得るのか。追加した後に末端の R な要素を削除すればこうなるはず。つうことは部分木としての削除なパタンというのは基本的に三世代の部分木であり得るケイスを表現可能なのか。
わしは実装からリバースで、だったんですが木の特徴が分かっていれば確かにこんな実装になりますね。でも上で列挙したソレが全てか、と言われると微妙な感触ではありますが。