どこかでみかけたHaskell版から翻訳してみた。Haskellの方がコンパクト。あと型チェックはないよね。

btree.rb

class Leaf
  def initialize(n)
    @value = n
  end
  def value
    @value
  end
  def size
    1
  end
  def sum
    @value
  end
  def avg
    @value
  end
  def max
    @value
  end
  def min
    @value
  end
  def map
    Leaf.new(yield(@value))
  end
  def find(n)
    if (n == @value)
      self
    else
      nil
    end
  end
end

class Branch
  def initialize(l,n,r)
    # should be: @l.value < n
    # should be: n < @r.value
    @l = l; @r = r
    @value = n
  end
  def value
    @value
  end
  def size
    @l.size + 1 + @r.size
  end
  def sum
    @l.sum + @value + @r.sum
  end
  def avg
    sum / size
  end
  def max
    @r.max
  end
  def min
    @l.min
  end
  def map(&b)
    Branch.new(@l.map(&b), yield(@value), @r.map(&b))
  end
  def find(n)
    if (n == @value)
      self
    elsif n < @value
      @l.find(n)
    else
      @r.find(n)
    end
  end
end

leaf = Leaf.new(10)
branch = Branch.new(Leaf.new(1), 2, Leaf.new(3))
p ["sum leaf", leaf.sum]
p ["sum branch", branch.sum]
p ["size leaf", leaf.size]
p ["size branch", branch.size]
p ["avg leaf", leaf.avg]
p ["avg branch", branch.avg]
p ["min leaf", leaf.min]
p ["max leaf", leaf.max]
p ["min branch", branch.min]
p ["max branch", branch.max]
p ["find branch 2", branch.find(2)]
p ["find branch 1", branch.find(1)]
p ["find branch 3", branch.find(3)]
p ["map leaf(*2)", leaf.map{|x|x*2}]
p ["map branch(*2)", branch.map{|x|x*2}]