二分探索木の子・兄弟表現

ペアリング・ヒープ (pdf) 向けとされている二分木の子・兄弟表現を二分探索木で使うとどうなるのか試してみました。 子・兄弟表現とは、 ノードの 2 つのポインタの一方を子ノードへのポインタ、 他方のポインタを兄弟もしくは親ノードへのポインタに変更したものです。 あるノード P の左子ノード L と右子ノード R をもつとき、 P の子ポインタは L へ、 L の兄弟ポインタは R へ、 R の兄弟ポインタは P へと循環参照させます。 子ノードが L しかないときは、 P の子ポインタを L へ、 L の兄弟ポインタを P にします。 同様に、 子ノードが R しかないときも、 P の子ポインタを R に、 R の兄弟ポインタを P にします。

                 ↑                                              ↑
     |P child sibling| ←---------------             |P child sibling| 
          ↓                            |                 ↓     ↑
     |L child sibling|  →  |R child sibling|      |L/R child sibling| 
          ↓                     ↓                       ↓

二分探索木の場合、 子ノードが一つしかないときでも、 ノードのキーと子ノードのキーの大小比較をすることで、 左か右かを区別できます。

class BinarySearchTree
  class Node
    attr_accessor :key, :child, :sibling
    def self.[](k, c, s) new(k, c, s) end
    def initialize(k, c, s) @key, @child, @sibling = k, c, s end

#@< parent@>
#@< left@>
#@< right@>
  end

  include Enumerable

  def initialize
    @top = Node[:top, nil, nil]
    @top.sibling = @top
  end

  def root() @top.left end
#@<find@>
#@<each@>
end

親ノードを求めるには、 兄弟ノードの先の循環参照を利用して、 自分に戻ることができるノードを探します。 上のように、 ルートをダミーの親ノードにつなぐことにして、 ダミーの兄弟をダミー自身にしておくと、 兄弟ノードの 2 つ先は必ず存在することになるので、 条件を単純にすることができます。

#@< parent@>=
    # 2つの子ノードの左ノードの親を求めるとき
    #   @sibling.sibling.child.equal?(self) ならば @sibling.sibling
    # 2つの子ノードの右ノードの親を求めるとき
    #   @sibling.child.sibling.equal?(self) ならば @sibling
    # 1つの子ノードの親を求めるとき
    #   @sibling.child.equal?(self) ならば @sibling
    def parent
      if @sibling.sibling.child.equal?(self)
        @sibling.sibling
      else
        @sibling
      end
    end

左の子ノードを求めるには、 nil でなくキーが小さい子ノードが子ポインタの先にあることを調べます。

#@< left@>=
    def left
      if @child and @child.key < @key
        @child
      else
        nil
      end
    end

右の子ノードは、 左の子ノードの兄弟ポインタにつなげてある場合と、 子ポインタに直接つながっている場合の、 2 種類がありえます。 兄弟ポインタは子ノードが 2 つのときは右ノードを、 1つのときは親ノードをさすので、 親ノードを指していないなら右ノードだと判断します。 そうでないときは、 子ノードのキーが大きいことをチェックします。

#@< right@>=
    def right
      if @child and not @child.sibling.equal?(self)
        @child.sibling
      elsif @child and @child.key > @key
        @child
      else
        nil
      end
    end

子・兄弟ポインタを直接扱って木からのキーの探索を書いてみましょう。 上の左右のポインタのふるまいを展開して、 コードを整理します。

#@<find@>=
  def find(key)
    node = @top.child
    not node.nil? or return nil
    while node.key != key
      child = node.child
      not child.nil? or return nil
      if key < node.key
        child.key < node.key or return nil
      elsif child.key < node.key and not child.sibling.equal?(node)
        child = child.sibling
      end
      node = child
    end
    node.key
  end

親ノードへのポインタを利用して間順走査をおこないます。 親から左の子へ降りたとき、 左から親へ登ったとき、 親から右の子へ降りたとき、 右から親へ戻ったときの 4 つの移動方向を判定して、 それぞれで次に移るべきノードを選択していくことで走査することができます。

#@<each@>=
  # Aristotle, ``Tree traversal without recursion: the tree as a state machine'' 
  # http://www.perlmonks.org/?node_id=600456
  def each
    return to_enum(:each) if not block_given? and respond_to?(:to_enum)
    prev, node = @top, @top.child
    not node.nil? or return
    while not node.equal?(@top)
      parent = node.parent
      if prev.equal?(parent)
        yield node.key if node.child.nil? or node.child.key > node.key
        node_next = node.child || parent
      elsif prev.equal?(node.child) or prev.equal?(node.child.sibling)
        node_next = parent
        if prev.key < node.key
          yield node.key
          node_next = prev.sibling if not prev.sibling.equal?(node)
        end
      else
        raise 'cannot happen'
      end
      prev, node = node, node_next
    end
  end

挿入・削除を子・兄弟ポインタを使って記述するのは、 まだ試していません。 そのうちできたら続編として投稿するかもしれません。