赤黒木 (26)

そろそろかなり gdgd になってきてるので、という訳でもないのですが最後のアレとゆーことで Gauche の test/treemap.scm の挿入、削除の試験を確認してみます。

まず追加から

これまでの確認で遅ればせながら追加であれば親の sibling の色がカギ。最初の状態以下から始めます。

  ;;    B:0
  ;;      R:1

ここから -1 が追加されて、さらに -2 が追加。

  ;;        R:-2
  ;;      R:-1
  ;;    B:0
  ;;      R:1

親は赤でその sibling なソレも赤。以下になって繰り返し。処理対象は R:0 な node になります。

  ;;        R:-2
  ;;      B:-1
  ;;    R:0
  ;;      B:1

とは言え、親が NULL になるので root が黒になって終了。

  ;;        R:-2
  ;;      B:-1
  ;;    B:0
  ;;      B:1

で、次に 2 が追加。

  ;;        R:-2
  ;;      B:-1
  ;;    B:0
  ;;      B:1
  ;;        R:2

これはそのまま終了ですね。次は上記に 1.5 な node が追加。

  ;;        R:-2
  ;;      B:-1
  ;;    B:0
  ;;      B:1
  ;;          R:1.5
  ;;        R:2

これは 4b 経由で 5b か。こうなるのかな。

  ;;        R:-2
  ;;      B:-1
  ;;    B:0
  ;;        R:1
  ;;      B:1.5
  ;;        R:2

あたり。こうしてみるに、確かに追加は理解しやすいんですが、親の sibling なソレが赤の場合の繰り返しの理解がもう少し足りない感。
とりあえず 5a なケイスまで確認して寝ます。-1.5 な要素が追加。

  ;;        R:-2
  ;;          R:-1.5
  ;;      B:-1
  ;;    B:0
  ;;        R:1
  ;;      B:1.5
  ;;        R:2

これは 4a -5a なのかな。n (追加される要素) は親の右で親はその親の左。こう回転して

  ;;          R:-2
  ;;        R:-1.5
  ;;      B:-1
  ;;    B:0
  ;;        R:1
  ;;      B:1.5
  ;;        R:2

色を変更。

  ;;          R:-2
  ;;        B:-1.5
  ;;      R:-1
  ;;    B:0
  ;;        R:1
  ;;      B:1.5
  ;;        R:2

これで R:-1 を基点に rotate_right すると以下。

  ;;        R:-2
  ;;      B:-1.5
  ;;        R:-1
  ;;    B:0
  ;;        R:1
  ;;      B:1.5
  ;;        R:2

とりあえず他の追加のケイスを確認してから削除も確認の方向です。あ、残りも 4[ab] から 5[ab] なケイスなのでスルーで良いな。

と、いうことで

明日のソレなネタは削除の試験掘削になるのか、はたまた別件なのか。