二分木の each メソッド

二分木を深さ優先で走査し、左から右へと辿る通りがけ順ですべてのノードと葉を順に yield する each を再帰呼び出しで記述すると、次のようになります。

  def each(&blk)
    each_rec(@root, &blk)
    self
  end

  def each_rec(t, &blk)
    if t.leaf?
      blk.call(t)
    else
      each_rec(t.left, &blk)
      blk.call(t)
      each_rec(t.right, &blk)
    end
  end

これを CEK マシンに直訳します。

  def each
    k = [:left, @root, :stop]
    while k != :stop
      case k.first
      when :left
        _, t, k = k
        if t.leaf?
          yield t
        else
          k = [:left, t.left, [:right, t, k]]
        end
      when :right
        _, t, k = k
        yield t
        k = [:left, t.right, k]
      end
    end
    self
  end

シンボル left でノードのとき、すぐにシンボル left にジャンプするため、 while で書き直せます。

  def each
    k = [:left, @root, :stop]
    while k != :stop
      case k.first
      when :left
        _, t, k = k
        while not t.leaf?
          k = [:right, t, k]
          t = t.left
        end
        yield t # 葉
      when :right
        _, t, k = k
        yield t # ノード
        k = [:left, t.right, k]
      end
    end
    self
  end

さらに、継続ループに入る前と、シンボル right の直後も必ず シンボル left をおこなうので、継続はシンボル right とシンボル stop だけで良いことになります。

  def each
    k = :stop
    t = @root
    while true
      while not t.leaf?
        k = [:right, t, k]
        t = t.left
      end
      yield t # 葉
      break if k == :stop
      _, t, k = k
      yield t # ノード
      t = t.right
    end
    self
  end

継続リストは、こうなるとパスの役割しかしていないため、配列にします。

  def each
    path = []
    t = @root
    while true
      while not t.leaf?
        path.push t
        t = t.left
      end
      yield t # 葉
      break if path.empty?
      t = path.pop
      yield t # ノード
      t = t.right
    end
    self
  end

ここまで自力であがいてみたわけですけど、これを D. KnuthThe Art of Computer Programming Vol.1 asin:0201896834 320 ページ記載の Algorithm T (Traverse binary tree in inorder) と比較したら、そのまんまで同じでした。

ところで、yield 対象がノードだけで良いとき、D. Knuthgoto 文を用いた構造的プログラミング (1974) asin:4756101909 87 ページによると、さらに改善できるそうです。つまり、最初の再帰版を次のように改良した場合のループ版にした方が良いということだそうです。

  def each_rec(t, &blk)
    if not t.leaf?
      if not t.left.leaf?
        each_rec(t.left, &blk)
      end
      blk.call(t)
      each_rec(t.right, &blk)
    end
  end

Knuth 先生の algol コードを Ruby に翻訳してみました。

  def each
    path = []
    t = @root
    while true
      if not t.leaf?
        while not t.left.leaf?
          path.push t
          t = t.left
        end
      elsif path.empty?
        break
      else
        t = path.pop
      end
      yield t
      t = t.right
    end
    self
  end

赤黒木とロープの each をこれらを使って書き改めておきました。