赤黒木 (27)

gauche

削除の試験確認メモです。と言いつつ昨晩の 3 な記述が微妙というか無い事に気づく。

と思ったらあった

以下な状態より

  ;;    B:0
  ;;      R:1
  • 1, -2, 2 を順に追加する模様。その中で -2 な要素を追加する時が insertion case 3 なソレになるのか。つうかこれって
  ;;      R:-1
  ;;    B:0
  ;;      R:1

な部分木のどちらかの子供に要素が追加されるケイスのみ、に限定されるんかな。確かに上記な部分木って頻出と言えば頻出ですね。
無理やり一般化な表現を用いるとすると上記な部分木に要素が追加された場合、以下な形にして

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

R:0 が追加されたものとして再度挿入処理を行なう、という事になるのかどうか。もしかすると試験としては記述されていないけど preparation の中でそうしたケイスになる追加処理もあるのかな、と思いはじめていたり。
でも、ここまで確認し始めるとキリが無いよなぁ。
とゆーことで削除頑張って確認してみます。

削除の試験確認メモ

まず、以下の状態から開始。

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

ここから 2 な要素を削除しますが、_deleting the leaf red node._なケイスはそのまま leaf node が削除されて終了。

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

次はいきなり 8a らしい。以下な状態から

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

削除の対象は B:1 な要素な模様。4[ab]、5、6、7[ab] に合致せず、8 のみ適用なパターンですね。確かに B:1 削除後の部分木が

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

になってるので 7[ab] 通過せずに 8[ab] で整形なのか。おそらくは B:1 削除後の部分木が

  ;;      R:1.5 => 1.5
  ;;          R:1.8 => 1.8
  ;;        B:2 => 2

みたくなってるとこれを真っ直にするよう 7a なナニが適用されるのね。ちなみに上の上の部分木は rotate_left でこうなるので

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

こうなって次の 8b な -1 の削除となる模様。

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

これは確かに 8b のみ通過な上の逆版ですね。詳細は略。やはり 7* および 8* については後処理としての部分木の整形になりますね。次は case 6 とのこと。B:-1 な要素を削除した後の以下のソレから

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

R:2 な要素が削除になる模様。これは delete_node1 手続きに入る前に swap_node で以下な部分木になって

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

6 のケイスになる、と。よくある

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

な部分木の親要素を削除するとこのケイスになるんスね。最終的には

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

となって終わるのかな。次はここから 1.5 な要素を削除する deletion case2 な模様。片方しか子供が居なくてその子供が赤の場合は

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

となって終わる模様。これ、scheme な rbtree.scm だとどの記述なんだろ。以下か。

  (let loop ((x x) (p p))
    (if (or (nil? p) (red? x))
      (unless (nil? x)
        (paint-black! x))

x は削除対象の子供の要素で p は削除対象の親の要素で、delete-fixup! 手続きに入る前にリンクは張り終えてますね。成程。次は deletion case5 とのこと。
以下なソレを作って

  ;;        B:-3 => -3
  ;;      B:-2 => -2
  ;;        B:-1.5 => -1.5
  ;;    B:0 => 0
  ;;          R:0.5 => 0.5
  ;;        B:1 => 1
  ;;      B:2 => 2
  ;;          B:2.5 => 2.5
  ;;        R:3 => 3
  ;;          B:3.5 => 3.5
  ;;            R:4 => 4
  • 3 な要素を削除な模様。繰り返しか。5 なケイスなのでこうなって
  ;;      B:-2 => -2
  ;;        R:-1.5 => -1.5
  ;;    B:0 => 0

parent が B:0、child が B:-2 になって繰り返して左に回転になる模様。これしかし綺麗に平衡になるなぁ。例えばこのケイスだと左半分が上になってから

  • sibling->color = parent->color ;; <- B:2 が黒に
  • parent->color = BLACK ;; <- B:0 が黒に
  • sibling->right->color = BLACK ;; <- R:3 が黒に
  • 左回転

で OK というのはすばらだなぁ。この繰り返しのパターンというのは上の通り、root から見て左側の部分木が薄くなるので回転させる、というのは分かるんですが、どうなんだろうか。
上の削除前の木で言うと左の削除される部分木は 3 の深さがあったのにそれが 2 の深さになってしまったので、一つ上に parent を移動して、ということなのか。
ちなみに逆側は当り前に深さは 3 なので、一つ上に移動してバランスを取るようにすれば良い、ということなのか。これ、

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

な部分木を持つ親の色は何があり得るのか、は気になります。

そろそろ終わり

と言いつつなかなか終わらんな。やはり赤黒なソレは繰り返しに深い何かが隠されているように思えます。
ということで今日はそろそろクタバりますです。