赤黒木 その場書き換え版

赤黒木の平衡調整は、 綺麗に左右対称の記述になっています。 それを利用して、 crit-bit 木のように子への参照を 2 要素の配列にすることで、 左右の場合分けを一つにまとめることができます。 左をゼロの位置に、 右を 1 の位置に配置することにします。 前回のその場書き換え方式を元にしつつも、 今回は親の参照を省いています。 根はダミー節の左につなぐことにします。

module RedBlack
  class Node
    attr_accessor :color, :key
    attr_reader :child

    def initialize(color, key, left, right)
      @color, @key, @child = color, key, [left, right]
    end
  end

  class Tree
    def initialize() @top = Node.new(:black, nil, nil, nil) end
    def root() @top.child[0] end

#@< 木に値を挿入します@>
#@< 値を削除します@>
#@< 挿入で崩れた平衡を調整します@>
#@< 削除で崩れた平衡を調整します@>
#@< 節と葉の色を調べます@>
#@< 木を回転します@>
  end
end

赤色になれるのは節だけです。 葉は常に黒色で、 節は黒色になることもできます。

#@< 節と葉の色を調べます@>=
    def red?(x) x.respond_to?(:color) && x.color == :red end
    def black?(x) ! x.respond_to?(:color) || x.color == :black end

回転は左右兼用しています。 回転方向は mside で示し、 mside が左 (0) のときは右回転、 右 (1) のときは左回転します。 回転対象は節 q の qside にある節 m です。節 m の mside 側の節 n が回転後に節 q の中の節 m があった位置に移動します。 親の色は新しい親に引き継ぎ、 新しい子は指定した色に塗ります。

#@< 木を回転します@>=
    # mside==0 rotate right; mside==1 rotate left.
    def rotate(q, qside, mside, color)
      m = q.child[qside]
      n = m.child[mside]
      q.child[qside] = n
      m.child[mside] = n.child[1 - mside]
      n.child[1 - mside] = m
      n.color, m.color = m.color, color
    end

まず木からの削除から。 葉のすぐ上まで降りる際に、 どの節のどちら側に降りたのかを配列 path に記録していきます。

#@< 値を削除します@>=
    def erase(x)
      @top.child[0] or return self
      path = [@top, 0]
      node = @top.child[0]
      while x != node.key
        side = x < node.key ? 0 : 1
        node.child[side] or return self
        path << node << side
        node = node.child[side]
      end
      if node.child[0]
        hit = node
        path << node << 0
        node = node.child[0]
        while node.child[1]
          path << node << 1
          node = node.child[1]
        end
        hit.key = node.key
      end
      parent, pside = path.pop(2)
      parent.child[pside] = node.child[1] || node.child[0]
      if black?(node)
        underflow(path, parent, pside)
      end
      @top.child[0].color = :black if red?(@top.child[0].color)
      self
    end

平衡調整は path を戻っていきます。 左右の場合分けの中身が左右対称なので、 指標を使うことで、 一つにまとめることができます。 親を挟んだ反対側の節の色の配置によって、 併合・再配分のどれをおこなうかが決まり、 反対側は 1 から指標を引くことで求めることができます。

#@< 削除で崩れた平衡を調整します@>=
    def underflow(path, parent, pside)
      if red?(parent.child[pside])
        parent.child[pside].color = :black
        return
      end
      while not parent.equal?(@top) and black?(parent)
        sibl = parent.child[1 - pside]
        (black?(sibl) and black?(sibl.child[0]) and black?(sibl.child[1])) or break
        sibl.color = :red
        parent, pside = path.pop(2)
      end
      not parent.equal?(@top) or return
      grand, gside = path.pop(2)
      sibl = parent.child[1 - pside]
      if black?(parent) and red?(sibl)
        rotate(grand, gside, 1 - pside, :red)
        grand, gside = sibl, pside
      end
      sibl = parent.child[1 - pside]
      if red?(parent) and black?(sibl.child[0]) and black?(sibl.child[1])
        parent.color, sibl.color = :black, :red
      else
        if red?(sibl.child[pside]) and black?(sibl.child[1 - pside])
          rotate(parent, 1 - pside, pside, :red)
        end
        parent.child[1 - pside].child[1 - pside].color = :black
        rotate(grand, gside, 1 - pside, :black)
      end
    end

今度は挿入です。 葉へ降りていくとき、 どの節のどちらに降りたかを path に記録するのは削除と一緒です。

#@< 木に値を挿入します@>=
    def insert(x)
      if @top.child[0].nil?
        @top.child[0] = Node.new(:black, x, nil, nil)
      else
        path = [@top, 0]
        node = @top.child[0]
        while true
          x != node.key or return self
          side = x < node.key ? 0 : 1
          path << node << side
          if node.child[side].nil?
            node = node.child[side] = Node.new(:red, x, nil, nil)
            break
          end
          node = node.child[side]
        end
        overflow(path, node)
        @top.child[0].color = :black
      end
      self
    end

赤が 2 連になっているときは、 平衡調整します。 これも左右対称なので、 指標を使うことで左右の場合分けを一つにまとめることができます。

#@< 挿入で崩れた平衡を調整します@>=
    def overflow(path, node)
      while red?(node) and red?(path[-2])
        parent, pside = path.pop(2)
        grand, gside = path.pop(2)
        uncle = grand.child[1 - gside]
        red?(uncle) or break
        parent.color, grand.color, uncle.color = :black, :red, :black
        node = grand
      end
      if red?(node) and red?(parent)
        base, bside = path.pop(2)
        if gside != pside
          rotate(grand, gside, pside, :red)
        end
        rotate(base, bside, gside, :red)
      end
    end