赤黒木 (14)

gauche

朝練メモ。ここから順に 2 と -1 な要素が削除される模様。

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

以下なコメントがあります。

  ;;   case 3.  this goes through parent==NULL stop condition in the
  ;;            loop in delete_node1.

確かに key が 2 な要素は root になっています。順に確認を。
delete-node! 手続きから

  (let1 z (if (and (not (nil? (left z))) (not (nil? (right z))))
            (let1 y (successor z)
              (set! (ref z 'key) (ref y 'key))
              (set! (ref z 'value) (ref y 'value))
              y)
            z)

む、今回は z の左右の子供は nil ではないですね。ええと successor は次に大きい key の要素を戻すはずなので、key が 2.5 な要素を戻すのか。z がそれにおきかわるのかな。あ、z の key と value も置き換えられるのか。あー、入れ替えて元あった方を削除するのか。

    (let ((x (left* z (not (nil? (left z)))))
          (p (parent z)))

x には nil、p は key が 3 の要素、になるのかどうか。

      (unless (nil? x)
        (set! (parent x) p))

x が nil なのでここはスルー。

      (if (nil? p)
        (set! (root-of tree) x)
        (set! (left* p (eq? z (left p))) x))

p は nil ではないので、key が 3 の左の子供な key が 2.5 な要素は切り離し。

      (when (black? z)
        (delete-fixup! tree x p))

z は黒なので delete-fixup! 呼び出されます。この時点での tree は以下?

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

引数な x は nil で p は key が 3 な要素を指してます。

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

p は nil でなく、x も黒 (nil) なのでここはスルー。

      (let1 b (eq? x (left p))
        (let1 w (let1 w (right* p b)
                  (if (red? w)
                    (begin (paint-black! w)
                           (paint-red! p)
                           (left-rotate! tree p b)
                           (right* p b))
                    w))

b は #t ですね。p の右は key が 3.5 の要素で黒なので w はこの要素を指します。

          (if (and (black? (left w)) (black? (right w)))
            (begin (paint-red! w)
                   (loop p (parent p)))

w の右側の子供は赤なのでここもスルー。

            (let1 w (if (black? (right* w b))
                      (begin (unless (nil? (left* w b))
                               (paint-black! (left* w b)))
                             (paint-red! w)
                             (right-rotate! tree w b)
                             (right* p b))
                      w)

右側の子供は赤なのでここもスルーで w は key が 3.5 の要素を指したまま。

              (set! (ref w 'color)
                    (if (nil? p) 'black (ref p 'color)))
              (paint-black! p)
              (paint-black! (right* w b))
              (left-rotate! tree p b)
              (paint-black! (root-of tree)))))))))
  • w の色は p の色に、ですが両方黒なので変わらず
  • p を黒に
  • w の右を黒に、なので key が 4 の要素は黒になります

で、left-rotate! 呼び出し前の tree が以下になるのか。

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

p は key が 3 の要素を指してる状態で b は #t か。

  (let1 y (right* x b)

y は key が 3.5 の要素を指す。

    (set! (right* x b) (left* y b))
    (unless (nil? (left* y b))
      (set! (parent (left* y b)) x))

ええと、これって

  ;;    B:2.5 => 2.5
  ;;      B:3 => 3
  ;;        B:3.5 => 3.5
  ;;          B:4 => 4

が

  ;;    B:2.5 => 2.5
  ;;        B:3 => 3
  ;;      B:3.5 => 3.5
  ;;        B:4 => 4

てなるんだっけ。とりあえず y は x の右から切り離されてます。

    (set! (parent y) (parent x))

で、y の親は x の親に。key が 3.5 の親は key が 2.5 の要素になりますね。

    (cond ((nil? (parent x))
           (set! (root-of tree) y))
          ((eq? x (left* (parent x) b))
           (set! (left* (parent x) b) y))
          (else
           (set! (right* (parent x) b) y)))

x はその親の右側要素なので、ということで親からのリンクを張り直しています。

    (set! (left* y b) x)
    (set! (parent x) y)))

で、x を y の左にして終了。こうなりました。

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

これで 2 の削除が終了。次が -1 な要素の削除になりますが、タイムアップ。