赤黒木 (8)

insertion case 4a. および insertion case 4b. の確認。

insertion case 4a

ええと初期状態が以下で

  ;;          R:-4
  ;;        B:-3
  ;;          R:-2
  ;;      R:-1
  ;;          R:-0.7
  ;;        B:-0.5
  ;;    B:0
  ;;      B:2.5
  ;;        R:4

ここに -0.6 な要素を追加するようです。最初はこうなるんかな。

  ;;          R:-4
  ;;        B:-3
  ;;          R:-2
  ;;      R:-1
  ;;          R:-0.7
  ;;            R:-0.6
  ;;        B:-0.5
  ;;    B:0
  ;;      B:2.5
  ;;        R:4

これは単に left-rotate! から right-rotate! のパターンなのかな。確認します。上記の状態で put-fixup! が呼び出されます。

(define (put-fixup! tree z)
  (let loop ((z z))
    (when (red? (parent z))
      (let* ((b (eq? (parent z) (left (parent (parent z)))))
             (y (right* (parent (parent z)) b)))

• z (key が -0.6) の親は無論赤 (key が -0.7)
• z の親はそのまた親の左側の要素なので b は真
• z の親の対面は nil なので (key が -0.5 の要素の右側要素は nil) y も nil

というあたりを前提にするとまず

        (if (red? y)

は偽なので以下なブロックが評価されます。

          (let1 z (if (eq? z (right* (parent z) b))
                    (begin0 (parent z)
                            (left-rotate! tree (parent z) b))
                    z)
            (paint-black! (parent z))
            (paint-red! (parent (parent z)))
            (right-rotate! tree (parent (parent z)) b))))))

ええと、b は真で z の親に対して z は右側になりますね。ので if の then ブロックが評価されることになります。で、基本的には

• x (key が -0.7) の親の左要素は y(key が -0.6) の要素に
• y (key が -0.6) の左が x (key が -0.7) に
• x (key が -0.7) の親が y (key が -0.6) に

ということで

  ;;            R:-0.7
  ;;          R:-0.6
  ;;        B:-0.5

ということになるんですかね。これはこのまんま

  ;;          R:-0.7 => -0.7
  ;;        B:-0.6 => -0.6
  ;;          R:-0.5 => -0.5

になって終わりなカンジですね。insertion case 4b も同様なカンジ。

とゆーことで

例のソレな分岐は通過しない、ということなのかな。Shiro さんの treemap の実装も別途精査できればと思ってます。明日以降で削除なナニを精査の方向にて。