バイナリツリーの再設計

日本Rubyの会 公式Wiki - Ruby勉強会＠関西-17で添削していたバイナリツリーのプログラムを仕様の継承をあきらめて再設計したらどうなるかなと思ってやってみました。どことなく関数型のにおいがします。

module BinaryTree
  def to_tree(ns)
    ns.inject(Node.new) {|tree, n| tree << n }
  end
  module_function :to_tree

  class Node
    def initialize(data = nil)
      @data = data
      @left = nil
      @right = nil
    end

    def <<(data)
      case
      when @data.nil?    then @data = data
      when @data == data then # ignore
      when @data > data  then (@left  ||= Node.new) << data
      when @data < data  then (@right ||= Node.new) << data
      end
      self
    end

    def trace(data)
      case
      when @data.nil?    then '*'
      when @data == data then @data.inspect
      when @data > data  then @left  ? "#{@data}-L-#{@left.trace(data)}"  : '*'
      when @data < data  then @right ? "#{@data}-R-#{@right.trace(data)}" : '*'
      end
    end
  end
end

if $0 == __FILE__
  ns = [17, 20, 13, 32, 47, 9, 50, 48]
  puts ns.join(' ')   # => 17 20 13 32 47 9 50 48

  tree = BinaryTree.to_tree(ns)
  puts tree.trace(50) # => 17-R-20-R-32-R-47-R-50
  puts tree.trace(1)  # => 17-L-13-L-*
  puts tree.trace(9)  # => 17-L-13-L-9
end

以下、変更点というか設計時に気を付けたこと。

• 全体をmoduleにして、バイナリツリー生成用のメソッドを持たせました。
• ツリーの節はNodeクラスにしました。
• 追加するメソッド名を<<にしてselfを返すようにしました。tree << 1 << 2 << 3みたいに使えるように。
• IOを分離するため、traceメソッドは文字列を返すようにしました。このため、見付かったか見付からないかは、traceメソッドではわからなくなりました。これについては別途メソッドを設けた方がよいように思います。