非破壊操作型赤黒木の挿入と削除

今度は、非破壊操作型の赤黒木の挿入と削除を書いてみます。赤黒木に値を挿入すると、元の木には手をふれずに、値を挿入した新しい木を作って返します。変更を受けなかったノードは元の木と共用します。削除も同様です。クラスの大部分は破壊操作のものと同じですが、念のために属性のアクセッサをすべて読み出し専用にしておきます。そのうえで、new メソッドに根を渡して新しい木を作れるようにします。

非破壊操作型赤黒木の挿入と削除の手直し

2014-04-11 delete を修正

class RedBlacktree
  include Enumerable

  class Node
    attr_reader :color, :left, :data, :right

    #以下、Node クラスの内容は破壊操作型と同じなので略します
  end

  # NULL オブジェクトと consistend? や each 等も破壊操作型と同じなので略します

  attr_reader :root

  def initialize(root = NULL)
    @root = root
  end

#@<値を挿入した木を作成する@>

#@<値を削除した木を作成する@>
end

非破壊操作の挿入処理は、破壊操作よりも簡潔になります。探索経路を葉から根へと、ノードを作ってつなげながら逆戻りするだけで良いからです。簡潔になった代償に、非破壊操作では必ず根まで戻らなければなりません。破壊操作のときのように、途中で更新が不要になったからといって中断させることはできません。なお、次のコードで「挿入で崩れた木を整える」の箇所を削ると、ノードに色がついているのに目をつむれば、そのまま非破壊操作型 2 分探索木の挿入ルーチンになっています。

#@<値を挿入した木を作成する@>=
  def insert(x)
    path = []
    node = @root
    while not node.null?
      return self if x == node.data
      if x < node.data
        path.push [:left, node]
        node = node.left
      else
        path.push [:right, node]
        node = node.right
      end
    end
    r = Node.red(NULL, x, NULL)
    path.reverse_each do |fn, node|
      parent = r
      r = if fn == :left
          then Node.new(node.color, parent, node.data, node.right)
          else Node.new(node.color, node.left, node.data, parent)
          end
#@<   挿入で崩れた木を整える@>
    end
    r = Node.black(r.left, r.data, r.right) if r.red?
    self.class.new(r)
  end

挿入で崩れた木を整えるときも、ノードの内容を破壊操作せずに、新しくノードを作ってつなげます。探索経路上のすべてのノードを複製しないといけないため、黒ノードを複製するタイミングで木の崩れを整えることにします。調整が必要になる条件は、黒ノードの直下のどこかに赤ノードが2個連続してつながっているときです。この場合、2-3-4 木ノードがあふれた場合と、2 分 B 木ノードの対称性が崩れた 2 つの場合があるのは、非破壊操作でも同じです。あふれたときは 3 つに分割し、対称性が崩れたときはまんなかが黒ノードになるように回転をおこないます。

#@<   挿入で崩れた木を整える@>=
      next unless r.black? and parent.red?
      next unless parent.left.red? or parent.right.red?
      if r.sibling(parent).red?
        m, n = r.left, r.right
        r = Node.red(Node.black(m.left, m.data, m.right), r.data, Node.black(n.left, n.data, n.right))
      elsif fn == :left
        if parent.left.red?
          m, n, p2 = parent.left, parent, parent.left.right
        else
          m, n, p2 = parent, parent.right, parent.right.left
        end
        r = Node.black(Node.red(m.left, m.data, p2), n.data, Node.red(n.right, r.data, r.right))
      else
        if parent.right.red?
          m, n, p4 = parent, parent.right, parent.right.left
        else
          m, n, p4 = parent.left, parent, parent.left.right
        end
        r = Node.black(Node.red(r.left, r.data, m.left), m.data, Node.red(p4, n.data, n.right))
      end

削除も挿入と同じで探索経路を葉から根へ逆戻りしつつノードを複製してつなげていきます。その途中に削除対象のノードがあると、削除した末端のノードの値にさしかえますないといけません。そのため、あらかじめ、just_data 変数に削除対象のノードの値を記録しておきます。これまた、非破壊操作型 2 分探索木の削除処理と同じです。

#@<値を削除した木を作成する@>=
  def delete(x)
    path = []
    node, j, just = @root, nil, nil
    while not node.null?
      j, just = path.size, node if x == node.data
      if x <= node.data
        path.push [:left, node]
        node = node.left
      else
        path.push [:right, node]
        node = node.right
      end
    end
    return self if just.nil?
    fn, node = *path.pop
    if not just.equal?(node)
      path[j][1] = Node.new(just.color, just.left, node.data, just.right)
    end
    r = if fn == :left then node.right else node.left end
#@< 削除したノードの色を決める@>
    path.reverse_each do |fn, node|
      child = r
      r = if fn == :left
          then Node.new(node.color, child, node.data, node.right)
          else Node.new(node.color, node.left, node.data, child)
          end
#@<   削除で崩れた木を整える@>
    end
    self.class.new(r)
  end

#@<左側削除時のバランスをとる@>

#@<右側削除時のバランスをとる@>

削除では崩れた木の調整が終わったかどうかを記録している balanced 変数を使います。これが真のときは、調整が終わっており、ノードを複製するだけで良いことを示します。末端のノードの色の配置関係によって、調整が完了していることがあり、それを複製ループに入る前に調べます。

#@< 削除したノードの色を決める@>=
    balanced = false
    if node.red?
      balanced = true
    elsif r.red?
      balanced = true
      r = Node.black(r.left, r.data, r.right)
    end

探索経路を戻っていく途中で、削除で崩れた木を整えるときも、ノードの複製を使います。

#@<   削除で崩れた木を整える@>=
      next if balanced
      s = r.sibling(child)
      if r.black? and s.left.black? and s.black? and s.right.black?
        r = if fn == :left
            then Node.black(r.left, r.data, Node.red(s.left, s.data, s.right))
            else Node.black(Node.red(s.left, s.data, s.right), r.data, r.right)
            end
        next
      end
      if fn == :left
        r = if r.black? and s.red?
            then Node.black(balance_left(:red, r.left, r.data, s.left), s.data, s.right)
            else balance_left(r.color, r.left, r.data, s)
            end
      else
        r = if r.black? and s.red?
            then Node.black(s.left, s.data, balance_right(:red, s.right, r.data, r.right))
            else balance_right(r.color, s, r.data, r.right)
            end
      end
      balanced = true

左側削除時にバランスをとるには、2-3-4 木ノードとして見たとき、値の左右の下方向リンク先にある 2-3-4 木ノードの内容を寄せ集めて、左右対称な 2 分木ノードを組み立てます。

#@<左側削除時のバランスをとる@>=
  def balance_left(c, p0, d1, q)
    if q.left.black? and q.right.black?
      Node.black(p0, d1, Node.red(q.left, q.data, q.right))
    else
      if q.left.red? and q.right.black?
        p2, d3, p4, d5, p6 = q.left.left, q.left.data, q.left.right, q.data, q.right
      else
        p2, d3, p4, d5, p6 = q.left, q.data, q.right.left, q.right.data, q.right.right
      end
      Node.new(c, Node.black(p0, d1, p2), d3, Node.black(p4, d5, p6))
    end
  end

右側削除時にバランスをとるには、左削除時から左右対称に変えます。

#@<右側削除時のバランスをとる@>=
  def balance_right(c, q, d5, p6)
    if q.left.black? and q.right.black?
      Node.black(Node.red(q.left, q.data, q.right), d5, p6)
    else
      if q.left.black? and q.right.red?
        p0, d1, p2, d3, p4 = q.left, q.data, q.right.left, q.right.data, q.right.right
      else
        p0, d1, p2, d3, p4 = q.left.left, q.left.data, q.left.right, q.data, q.right
      end
      Node.new(c, Node.black(p0, d1, p2), d3, Node.black(p4, d5, p6))
    end
  end