赤黒木 (23)

昨日の件、

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

上記の状態になり、parent が B:0 で child が B:-1.5 になった時点で終了してます。見返しててびっくり仰天。ここから再度 case5 に入って B:3 の要素の色が赤くなって child が B:0 で parent が NULL になって終了、が正解でした。
最終的に木は以下になりますね。

  ;;      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

これは test/treemap.scm のコメントと同じです。赤黒木てきにも平衡。

どうもいかん

台風疲れだ。