binarytree.rb

module BinaryTree
  class Node
    attr_reader :word, :count, :left, :right

    include Enumerable

    def initialize(word)
      @word, @count = word, 1
    end

    def size
      size = 1
      size += @left.size  unless left.nil?
      size += @right.size unless right.nil?
      size
    end

    def insert(another_one)
      case @word <=> another_one.word
        when 1
          insert_into(:left, another_one)
        when 0
          @count += 1
        when -1
          insert_into(:right, another_one)
      end
    end

    def each
      @left.each {|node| yield node } unless @left.nil?
      yield self
      @right.each {|node| yield node } unless @right.nil?
    end

    def words
      entries.map {|e| e.word }
    end

    def count_all
      self.map { |node| node.count }.reduce(:+)
    end

    def insert_into(destination, another_one)
      var = destination.to_s
      eval(%Q{
        if @#{var}.nil?
          @#{var} = another_one
        else
          @#{var}.insert(another_one)
        end
      })
    end

    protected :insert_into
  end
end

binarytree_spec.rb

require 'rspec'
require './binarytree'

include BinaryTree

describe Node do
  share_examples_for 'Node with word "foo"' do
    its(:word)  { should == 'foo' }
  end

  share_examples_for 'Node with one child with no children' do
    its(:size) { should == 2 }
  end

  share_examples_for 'Node with two children with no children' do
    its(:size) { should == 3 }
  end

  share_examples_for 'Node with no children' do
    its(:left)  { should be_nil }
    its(:right) { should be_nil }
  end

  context 'with word "foo" and no children' do
    subject { Node.new('foo') }

    it_should_behave_like 'Node with word "foo"'
    it_should_behave_like 'Node with no children'

    its(:size)  { should == 1 }
    its(:count) { should == 1 }
    its(:words) { should == ['foo'] }
    its(:count_all) { should == 1 }
  end

  context 'with word "foo" and inserted a node with word "bar"' do
    before do
      @node = Node.new('foo')
      @node.insert(Node.new('bar'))
    end

    subject { @node }

    it_should_behave_like 'Node with word "foo"'
    it_should_behave_like 'Node with one child with no children'

    its(:right) { should be_nil }
    its(:words) { should == ['bar', 'foo'] }
    its(:count_all) { should == 2 }

    describe 'its child on the left' do
      subject { @node.left }

      it_should_behave_like 'Node with no children'

      its(:word)  { should == 'bar' }
      its(:size)  { should == 1 }
      its(:count) { should == 1 }
      its(:count_all) { should == 1 }
    end
  end

  context 'with word "foo" and inserted a node with word "hoge"' do
    before do
      @node = Node.new('foo')
      @node.insert(Node.new('hoge'))
    end

    subject { @node }

    it_should_behave_like 'Node with word "foo"'
    it_should_behave_like 'Node with one child with no children'

    its(:left)  { should be_nil }
    its(:words) { should == ['foo', 'hoge'] }
    its(:count_all) { should == 2 }

    describe 'its child on the right' do
      subject { @node.right }

      it_should_behave_like 'Node with no children'

      its(:word)  { should == 'hoge' }
      its(:size)  { should == 1 }
      its(:count) { should == 1 }
      its(:count_all) { should == 1 }
    end
  end

  context 'with word "foo" and inserted a node with word "foo"' do
    subject do
      node = Node.new('foo')
      node.insert(Node.new('foo'))
      node
    end

    it_should_behave_like 'Node with word "foo"'
    it_should_behave_like 'Node with no children'

    its(:count) { should == 2 }
    its(:words) { should == ['foo'] }
    its(:count_all) { should == 2 }
  end

  context 'with word "foo" and inserted a node with word "bar" 3 times' do
    before do
      @node = Node.new('foo')
      3.times { @node.insert(Node.new('bar')) }
    end

    subject { @node }

    it_should_behave_like 'Node with word "foo"'

    its(:right) { should be_nil }
    its(:count) { should == 1 }
    its(:size)  { should == 2 }
    its(:words) { should == ['bar', 'foo'] }
    its(:count_all) { should == 4 }

    describe 'its child on the left' do
      subject { @node.left }

      its(:word)  { should == 'bar' }
      its(:size)  { should == 1 }
      its(:count) { should == 3 }
      its(:count_all) { should == 3 }
    end
  end

  context 'with word "foo" and inserted a node with word "hoge" 3 times' do
    before do
      @node = Node.new('foo')
      3.times { @node.insert(Node.new('hoge')) }
    end

    subject { @node }

    it_should_behave_like 'Node with word "foo"'

    its(:left)  { should be_nil }
    its(:count) { should == 1 }
    its(:size)  { should == 2 }
    its(:words) { should == ['foo', 'hoge'] }
    its(:count_all) { should == 4 }

    describe 'its child on the right' do
      subject { @node.right }

      its(:word)  { should == 'hoge' }
      its(:size)  { should == 1 }
      its(:count) { should == 3 }
      its(:count_all) { should == 3 }
    end
  end

  context 'with word "a" and inserted nodes with word "b" ~ "j"' do
    before do
      @node = Node.new('a')
      %w{b c d e f g h i j}.each do |word|
        @node.insert(Node.new(word))
      end
    end

    subject { @node }

    its(:size)  { should == 10 }
    its(:words) { should == %w{a b c d e f g h i j} }
  end
end

example.rb

require './binarytree'

include BinaryTree

$root = nil
%w{to be or not to be}.each do |word|
  if $root.nil?
    $root = Node.new(word)
  else
    $root.insert(Node.new(word))
  end
end

$root.each do |node|
  puts "#{node.word} (#{node.count})"
end

puts
puts "#{$root.size} words."
puts "#{$root.count_all} nodes."