赤黒木 (15) # スルー推奨 - yamanetoshi's diary

へろへろな週末も終わろうかという時にやや復活気味なのでこちら方面に着手してみます。前回の継続はというと

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

となった tree から -1 な key の要素を削除して以下になれば OK なのですが。

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

なんか違うな。1 な要素が残ってるのはどーゆー事だ。

確認したところ

上記から 1 な要素を削除する所が継続らしい。結構激しく回転しそうなカンジ。

  (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)

key が 1 な要素は子供が居ないので z はそのまま。

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

x は z の右の nil で p は key が 0 の要素。

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

スルー。

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

親から z へのリンクが切られた上で

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

z は黒なので delete-fixup! が呼び出されます。

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

p は nil でもなく、x は黒なのでこのブロックはスルー。

      (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))

x は p の右なので #f ですね。w は p の左の要素で R:-1 なソレ。赤なので left-rotate! でもごもごされる模様。その前に

    B:-1.5
  B:-1
    B:-0.5
R:0

みたいな部分木になって left-rotate! に渡されます。

  (let1 y (right* x b)

とりあえず y は B:-1 な要素を指します。b は #f なので左の子供になります。

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

y の右は B:-0.5 な要素。R:0 の左の子供がこれにされます。

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

y の右は nil ではないので B:-0.5 な要素の親が R:0 になるのか。このケイスもはじめて見ますね。

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

で、y (B:-1) の親を x (R:0) の親 (B: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)))

なんですが (eq? x (left* (parent x) b)) は偽なので、親要素 (B:2.5) の左を y (B:-1) にします。で

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

をナニして以下な部分木になる模様。

  B:-1.5
B:-1
    B:-0.5
  R:0

大丈夫かな。これで終了かな。つうことは B:1 な要素を削除したら以下になるのか。

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

一応平衡。面白いな。ここから

あー違う

以下から B:1 が削除されるのかorz

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

ごめんなさい、今回のエントリはスルーでお願いします。
# じゃエントリすんな、という話もありますがそこはスルーでorz