赤黒木による順序付き集合

Guy E. Blelloch, et. al., "Just Join for Parallel Ordered Sets" (2016) のアルゴリズムruby に直訳することで、 赤黒木の非破壊 join 関数で順序付き集合演算を書いていきます。

join 関数は既に見たように、 2本の木の間にキーをはさんで新しい木を求める働きをします。 この関数は、 左側の木に含まれるすべてのキーは新しくはさみたいキーよりも小さく、 右側の木に含まれるすべてのキーは大きいことを、 前提にしていました。 この前提があるため、 join 関数はキーの大小関係は事前に解決済みとして、 バランス崩れの調整に専念できていました。

join 関数がうまく動作するには、 あらかじめ指定したキーよりも小さなキーだけを含む木と、 大きなキーだけを含む木に分割しておく必要があります。 その機能を提供するのが、 split 関数です。 指定したキーとの大小比較をおこないながら、 木を根から葉へと降りていき、 見つからなかったときも見つかったときも根へ戻りながら、 指定したキーよりも小さなキーを含む木と大きなキーを含む木それぞれを join 関数を使って組み立てます。 この関数は、 3 つの値の組を返します。 組の先頭に小さなキーだけを含む木、 中央にキーを含んでいるかどうかを示す真偽値、 組の最後に大きなキーだけを含む木が入ります。

  def split(tree, key)
    if tree.null?
      [NULL, false, NULL]
    else
      if key == tree.key
        [tree.left, true, tree.right]
      elsif key < tree.key
        tree_prime_ll, b, tree_prime_lr = split(tree.left, key)
        [tree_prime_ll, b, join(tree_prime_lr, tree.key, tree.right)]
      else
        tree_prime_rl, b, tree_prime_rr = split(tree.right, key)
        [join(tree.left, tree.key, tree_prime_rl), b, tree_prime_rr]
      end
    end
  end

split 関数でキーからの大小で分割した 2 本の木の間にキーをはさんで join すると挿入したことになります。

  def insert_into_tree(tree, key)
    tree_prime_left, _, tree_prime_right = split(tree, key)
    join(tree_prime_left, key, tree_prime_right)
  end

2 本の木のうち、 一方に含まれるキーを木の入れ子構造を辿りながら、 もう一方をそのキーで分割し、 それぞれに再帰的に挿入をおこなっていくと、 両方の木に含まれるすべてのキーをもつ木を効率良く作ることができます。

  def union_tree(tree1, tree2)
    if tree1.null?
      tree2
    elsif tree2.null?
      tree1
    else
      left1, _, right1 = split(tree1, tree2.key)
      tree_left = union_tree(left1, tree2.left)
      tree_right = union_tree(right1, tree2.right)
      join(tree_left, tree2.key, tree_right)
    end
  end

木からキーを削除した新しい木を作るには、 split 関数で分割した 2 本の木を間にキーを挟まずに連結しなければなりません。

  def delete_from_tree(tree, key)
    tree_left, _, tree_right = split(tree, key)
    join2(tree_left, tree_right)
  end

一方、 join 関数は必ず間にはさむキーを必要とします。 そのため、 左側の木から最右側のキーを取り除いた木、 取り除かれた最右側のキー、 右側の木を join 関数で連結することにします。

  def join2(tree_left, tree_right)
    if tree_left.null?
      tree_right
    else
      tree_prime_left, key_last = split_last(tree_left)
      join(tree_prime_left, key_last, tree_right)
    end
  end

左側の木を、 最右側のキーを取り除いた木と最右側のキーに分けるには、 左側の最右の葉の直上まで降りて、 join 関数で最右側のキーを取り除いた木のバランスを調整します。

  def split_last(tree)
    if tree.right.null?
      [tree.left, tree.key]
    else
      tree_prime_right, key_last = split_last(tree.right)
      [join(tree.left, tree.key, tree_prime_right), key_last]
    end
  end

このように、 キーを削除するのに、 split 関数を使って指定したキーの前後で木を分割し、 分割した左側の木をさらに最右キーとそれ以外の木に分割し、 指定したキー以外を join 関数で連結しています。 このやりかたは、 2分探索木でキーを削除するときの方法と同じで、 それを join 関数を使って書き直したわけです。

join2 関数を使うことで、 tree1 から tree2 に含まれるキーを取り除く関数を作れます。 tree2 の入れ子構造に従い、 tree2 のキーで tree1 を分割し、 それぞれに再帰的に取り除きをおこなってから join2 関数で連結していきます。

  def difference_tree(tree1, tree2)
    if tree1.null?
      NULL
    elsif tree2.null?
      tree1
    else
      left1, _, right1 = split(tree1, tree2.key)
      tree_left = difference_tree(left1, tree2.left)
      tree_right = difference_tree(right1, tree2.right)
      join2(tree_left, tree_right)
    end
  end

tree1 と tree2 の両方に含まれるキーだけを抽出するには、 split 関数で求まる組の中央にキーが含まれているかどうかを表す真偽値を使います。 tree1 を tree2 のキーで分割し、 含まれているときだけ、 そのキーをはさんで連結し、 含まれないときはキーをはさまずに連結します。

  def intersect_tree(tree1, tree2)
    if tree1.null?
      NULL
    elsif tree2.null?
      NULL
    else
      left1, b, right1 = split(tree1, tree2.key)
      tree_left = intersect_tree(left1, tree2.left)
      tree_right = intersect_tree(right1, tree2.right)
      if b
        join(tree_left, tree2.key, tree_right)
      else
        join2(tree_left, tree_right)
      end
    end
  end