破壊操作型赤黒木 その5 ノード非入れ替え回転

破壊操作型赤黒木 その3 値の挿入と回転 - Tociyuki::Diary の回転では、ノード・オブジェクトを入れ替えたので、回転操作が簡潔になる反面、親ノードからのポインタの付け替えが必要になりました。例えば、下のようにノード parent の right につながっているノード n を左回転するとき、ノード n の right につながっているノード m とノード n が入れ替わり、 回転後のノード parent の right はノード m へ変化します。

rotate_left(n, parent)

    #parent=<p d #n=<p0 d1 #m=<p2 d3 p4>>>
                             ↓
    #parent=<p d #m=<#n=<p0 d1 p2> d3 p4>>>

これに対して、上のノード parent とノード n の関係を変化させずに、 回転をおこなうやりかたがあります。この場合、ノード parent のポインタの置換が不要になるだけでなく、親がノードなのかルートなのかを気にせずに回転をおこなうことができます。

rotate_left(n)

    #parent=<p d #n=<p0 d1 #m=<p2 d3 p4>>>
                             ↓
    #parent=<p d #n=<#m=<p0 d1 p2> d3 p4>>>

後者では、ノード n と ノード m の両方のポインタとデータを書き換えます。ノードの色は変化させずにそのままにしておくことにします。

#@<木を回転する@>=

  def rotate_left(n)
    # #n=<p0 d1 #m=<p2 d3 p4>> => #n=<#m=<p0 d1 p2> d3 p4>
    p0, d1, p2, d3, p4 = n.left, n.data, n.right.left, n.right.data, n.right.right
    n.left = n.right
    n.left.left, n.left.data, n.left.right, n.data, n.right = p0, d1, p2, d3, p4
    n
  end

  def rotate_right(n)
    # #n=<#m=<p0 d1 p2> d3 p4> => #n=<p0 d1 #m=<p2 d3 p4>>
    p0, d1, p2, d3, p4 = n.left.left, n.left.data, n.left.right, n.data, n.right
    n.right = n.left
    n.left, n.data, n.right.left, n.right.data, n.right.right = p0, d1, p2, d3, p4
    n
  end

値を挿入する insert メソッドは回転を使わないので、そのままで使いまわせば良いでしょう。挿入で崩れた木の調整をする insert_rotations メソッドもほとんど変わらず、対称性崩れの調整時に色の付け替えがいらなくなる程度です。

#@<挿入で崩れた木の調整をする@>=
  def insert_rotations(path, node)
    g = parent = nil
    while true
      return node if path.empty?
      parent = path.pop
      return @root if parent.black?
      g = path.pop
      u = g.sibling(parent)
      break if u.black?
      parent.color, g.color, u.color = :black, :red, :black
      node = g
    end
    if g.left?(parent)
      if parent.right?(node)
        rotate_left(g.left)
      end
      rotate_right(g)
    else
      if parent.left?(node)
        rotate_right(g.right)
      end
      rotate_left(g)
    end
    @root
  end

値を削除する delete メソッドもそのまま使いまわせます。削除で崩れた木の調整をする delete_balancing は、手を入れる箇所が増えます。場合 1、2、3 の事前回転では、色替えが不要になると同時に s を新しく parent にしないといけません。場合 1 と 場合 2 では、赤から黒への色塗りが一ヶ所に減ります。

#@<削除で崩れた木の調整をする@>=
  def delete_balancing(path, child)
    node = path.pop
    return @root if node.red?
    if child.red?
      child.color = :black
      return @root
    end
    parent = path.pop
    while not parent.nil?
      s = parent.sibling(child)
      break unless [parent.black?, s.left.black?, s.black?, s.right.black?].all?
      # 場合 4.
      s.color = :red
      child = parent
      parent = path.pop
    end
    return @root if parent.nil?
    s = parent.sibling(child)
    if [parent.black?, s.left.black?, s.red?, s.right.black?].all?
      # 場合 1、2、3 の事前回転 #parent=[c dc:B #s=(p0 d1:R p1)] => [#s=(c dc:R p0) d1:B p1]
      if parent.left?(child)
        rotate_left(parent)
      else
        rotate_right(parent)
      end
      parent = s       # s が親になる。 => [#parent=(c dc:R p0) d1:B p1]
    end
    s = parent.sibling(child)
    if [parent.red?, s.left.black?, s.black?, s.right.black?].all?
      # 場合 3.
      parent.color, s.color = :black, :red
      return @root
    end
    if parent.left?(child)
      # 場合 1、2
      if s.left.red? and s.right.black?
        rotate_right(s)
      end
      s.right.color = :black if s.right.color == :red
      rotate_left(parent)
    else
      if s.left.black? and s.right.red?
        rotate_left(s)
      end
      s.left.color = :black if s.left.color == :red
      rotate_right(parent)
    end
    @root
  end

今回の回転操作の方が色の塗り換えが減っており、赤黒木の回転操作には、ポインタとデータをごっそりと入れ替えるやりかたの方がふさわしいようです。