二分木の子・兄弟表現 (その2)

二分木の通常の表現は、 左と右の子節への2つの参照を節にもたせます。 それに対して、 子と兄弟への2つの参照で表すのが子・兄弟表現です。 兄弟参照は左から右へと指して、 右から向きを変えて親を指すようにします。

前回は参照を素のままで二分探索木の表現に使ってみたものの、 使いにくかったので、 今度は節に 2 つの印を加えることにします。 印は 2 値で、 それぞれ 1 ビットしか使いません。 side 印は、 節が左の子なのか、 右の子なのかを表します。 値が left なら左の子、 right なら右の子とします。 これで、 親と子のキーの大小をいちいち調べなくても、 どちらの側の子なのかを知ることができます。 to 印は兄弟参照が指す相手が兄弟か親かを示します。 値が right なら右の兄弟を、 parent なら親を指します。 参照の循環構造をいちいち調べなくても兄弟か親のどちらを指しているのかすぐに判定可能です。

class BinarySearchTree
  Node = Struct.new(:key, :child, :sibling, :side, :to)
  # side == :left || :right,  to == :right || :parent

  def initialize
    @top = Node.new(nil, nil, nil, :left, :parent)
    @top.sibling = @top
  end

  def root() @top.child end

#@<insert@>
#@<erase@>
#@<assoc_internal@>
end

印の効用で、 子・兄弟表現のままで木の操作を記述するのが、 少し書きやすくなります。 子・兄弟表現であっても子の左右を判断しながら木を操作するのは同じです。 値の挿入では、 節のキーよりも値が小さいときは左の子へ降りていきます。 左に子がなくなり降りようとしても降りれない箇所に左側の節を追加します。 値が大きいときは右の子へ降りていき、 左同様に右側の節を追加します。 子・兄弟表現では子の参照に左だけでなく、 右がぶらさがっているときがあるので、 どちらの側の子かを判断しつつ、 参照を辿っていきます。

#@<insert@>=
  def insert(x)
    if @top.child.nil?
      @top.child = Node.new(x, nil, @top, :left, :parent)
    else
      node = @top.child
      while x != node.key
        if x < node.key
          if node.child.nil?
            node.child = Node.new(x, nil, node, :left, :parent)
            break
          elsif node.child.side == :left
            node = node.child
          else
            node.child = Node.new(x, nil, node.child, :left, :right)
            break
          end
        else
          if node.child.nil?
            node.child = Node.new(x, nil, node, :right, :parent)
            break
          elsif node.child.side == :right
            node = node.child
          elsif node.child.to == :right
            node = node.child.sibling
          else
            node.child.sibling = Node.new(x, nil, node, :right, :parent)
            node.child.to = :right
            break
          end
        end
      end
    end
    self
  end

削除は節を入れ替えて取り除く方法で書いています。 削除対象の節と、 左側でもっとも右にある節を入れ替えることで削除をおこないます。 これも左右表現と同じ方針で書いてあります。 挿入よりも複雑になっているのは、 nil の代入で節を抜く場合に対応するためと、 親への参照を適切に付け替えるためで、 それらを無視して読んでいくと、 左右表現と同じになっています。

#@<erase@>=
  def erase(x)
    node = assoc_internal(x) or return self
    g = node.parent
    r = node.child
    if r.nil? or r.side == :right
      # do nothing
    elsif r.child.nil?
      if r.to == :right
        r.child = r.sibling
      end
    elsif r.child.side == :left and r.child.to == :parent
      if r.to == :right
        r.child.sibling = r.sibling
        r.child.to = :right
      end
    else
      while r.child and (r.child.side == :right or r.child.to == :right)
        r = r.child.side == :right ? r.child : r.child.sibling
      end
      q = r.parent
      if r.child
        r.child.sibling = q
        r.child.side = :right
      end
      if q.child.side == :right
        q.child = r.child
      else
        q.child.sibling = r.child || q
        q.child.to = r.child ? :right : :parent
      end
      r.child = node.child
    end
    if r
      # 親への参照の更新
      r.sibling = node.sibling
      r.side = node.side
      r.to = node.to
      if r.child
        if r.child.to == :parent
          r.child.sibling = r
        else
          r.child.sibling.sibling = r
        end
      end
    end
    if g.child.equal?(node)
      g.child = (node.to == :parent) ? r : (r || node.sibling)
    else
      g.child.sibling = r || node.sibling
      g.child.to = r ? :right : :parent
    end
    self
  end

削除する節を見つけるのに assoc_internal メソッドを使っています。 挿入と同じ方式で値と節の値を比べつつ、 根から葉へと降りていきます。

#@<assoc_internal@>=
  def assoc_internal(x)
    not @top.child.nil? or return nil
    node = @top.child
    while x != node.key
      if x < node.key
        if node.child and node.child.side == :left
          node = node.child
        else
          return nil
        end
      else
        if node.child and node.child.side == :right
          node = node.child
        elsif node.child and node.child.to == :right
          node = node.child.sibling
        else
          return nil
        end
      end
    end
    node
  end

子・兄弟表現は 2 つの参照で左右の子と親への 3 つの参照を表しており、 木の再帰構造を直接表していないため、 扱うべき状況が増えてしまいます。 実際に試みたところ、 複雑さに見合うありがたみを感じることはありませんでした。 親への参照が欲しいときは、 左・右・親への 3 つの参照を素朴に節に持たせる方が良いように思えます。