破壊操作型赤黒木 その3 値の挿入と回転

赤黒木への値の挿入は、単なる 2 分探索木への挿入方法に手を加えていくことでおこなえます。変更点は、整合性が崩れたときに、木を調整するのに必要な経路を記録するところと、挿入するノードが赤色になることです。そして、部分木の回転と呼ばれる操作を組み合わせて、調整をおこないます。最後に、調整後にルートが赤色になってしまったとき、黒色に塗り直す後始末をやります。

#@<値を挿入する@>=
  def insert(x)
    return self.tap{ @root = Node.black(NULL, x, NULL) } if @root.null?
    path = []
    node = @root
    while true
      return self if x == node.data
      path.push node
      if x < node.data
        break if node.left.null?
        node = node.left
      else
        break if node.right.null?
        node = node.right
      end
    end
    if x < node.data
      node = node.left = Node.red(NULL, x, NULL)
    else
      node = node.right = Node.red(NULL, x, NULL)
    end
    @root = insert_rotations(path, node)
    @root.color = :black if @root.red?
    self
  end

#@<挿入で崩れた木の調整をする@>

部分木の回転操作とは、2 分木ノードの親と子の入れ子関係を変えることです。入れ子関係を変えても、左右の位置関係を変えないのが肝です。括弧の入れ子で部分木を表現すると、回転によって内側の括弧が左右に移動するように見えます。ところで、忘れてはならないのは、破壊型の挿入・削除では部分木がどこかに必ずぶらさがっているということです。そのため、ノードの親子関係を入れ換えたとき、元の親へのぶらさがりを元の子、つまり変換後の親へのぶらさがりへつけかえなければなりません。なので、回転操作には、回転対象の部分木とそれをぶらさげているノードの両方を指定することにします。回転すると、ぶらさがりを変更して、変換後に親になったノードを返します。

#@<木を回転する@>=
  def rotate_left(m, parent)
    # <p m <q n r>> => <<p m q> n r>
    #    ここで、<p m q> は黒ノード [p m q] または赤ノード (p m q) とする。
    n = m.right
    m.right, n.left = n.left, m
    subst_node(n, m, parent)
  end

  def rotate_right(n, parent)
    # <<p m q> n r> => <p m <q n r>>
    m = n.left
    n.left, m.right = m.right, n
    subst_node(m, n, parent)
  end

#@<ノードを置換する@>

ノードを置換するやりかたは、単純な 2 分探索木の削除メソッドで既に使っています。メソッドに切り出して形を整えておきます。

#@<ノードを置換する@>=
  def subst_node(node, for_node, parent)
    if parent.nil?
      @root = node
    elsif parent.left?(for_node)
      parent.left = node
    elsif parent.right?(for_node)
      parent.right = node
    else
      raise ArgumentError, 'parent should have for_node.'
    end
    node
  end

これらを使うと、挿入で崩れた木の調整をすることができます。挿入後の調整は 2-3-4 木ノードを黒ノードを中心にして眺めるのが理解しやすいでしょう。コメントは、黒ノード (g) の左側の部分木に赤ノード (n) を追加した状況を記入しています。整合性が崩れるのは赤が 2 つ連続する、つまり赤ノード (n) の親が赤ノード (p) のときです。 整合性が崩れているときは、さらに、2-3-4 木ノードがあふれた場合と、対称性が崩れたときの 2 通りがあって、while ループであふれた場合の調整を済ませます。どちらの場合かは、黒ノード (g) の反対側 (u) が赤か黒かで判定することができます。あふれたときは 2-3-4 木ノードを分割して、赤ノードを親 2-3-4 木ノードへ押し込みます。分割は色のつけかえだけで処理できます。対称性の崩れの調整は、部分木の回転と色のつけかえを組み合わせます。

#@<挿入で崩れた木の調整をする@>=
  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?
      # [((t0 n:R t1) p:R t2) g:B (t3 u:R t4)] => ([(t0 n:R t1) p:B t2] g:R [t3 u:B t4])
      # [(t0 p:R (t1 n:R t2)) g:B (t3 u:R t4)] => ([t0 p:B (t1 n:R t2)] g:R [t3 u:B t4])
      parent.color, g.color, u.color = :black, :red, :black
      node = g
    end
    if g.left?(parent)
      if parent.right?(node)
        # [(t0 p:R (t1 n:R t2)) g:B t3] => [((t0 p:R t1) n:R t2) g:B t3]
        rotate_left(g.left, g)
      end
      # [((t0 n:R t1) p:R t2) g:B t3] => [(t0 n:R t1) p:B (t2 g:R t3)]
      g.left.color, g.color = :black, :red
      rotate_right(g, path.last)
    else
      if parent.left?(node)
        rotate_right(g.right, g)
      end
      g.right.color, g.color = :black, :red
      rotate_left(g, path.last)
    end
    @root
  end