-
-
Save yuya-takeyama/812489 to your computer and use it in GitHub Desktop.
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 |
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 |
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." |
I feel like the initialize of the BinaryTree::Node is a bit confusing. In such a small case, it really doesn't make sense to me to use ruby's parallel assignment. In the interest of readable code, I think it would make more sense to do
def initialize(word)
@word = word
@count = 1
end
over
def initialize(word)
@word, @count = word, 1
end
Just my two cents. Regardless, this was extraordinarily helpful. Thanks!
Nice One..thanks :)
@yuya-takeyama thanks for posting this. I enjoyed using your specs to drive my own implementation while working on Ruby Kata 11: Sorting It Out.
Thanks for sharing.
Btw, it's not just a binary tree: it's a binary search tree.
Nice
How to find depth of the binary tree?
Hi @yuya-takeyama,
is it recursion function?
def size
size = 1
size += @left.size unless left.nil?
size += @right.size unless right.nil?
size
end
@Aravin, yes it is. When you call size
on the node, it calls size on each subsequent node. So when you reach the bottom of the tree, meaning node that doesn't have any children, it returns sum, which is 1 and then travels up.
I was searching for ruby tree implementations in web and this is the most easily understand implementation I found, thanks a lot. and RSpec tests are very valuable, learnt lots of new usages
thanks again