Skip to content

Instantly share code, notes, and snippets.

@dougjohnston
Forked from yuya-takeyama/binarytree.rb
Last active August 29, 2015 14:06
Show Gist options
  • Save dougjohnston/f3f1abc947eef51bf707 to your computer and use it in GitHub Desktop.
Save dougjohnston/f3f1abc947eef51bf707 to your computer and use it in GitHub Desktop.
Binary tree implemented in Ruby.
module BinaryTree
class Node
attr_reader :word, :count
attr_accessor :left, :right
include Enumerable
def initialize(word)
@word = word
@count = 1
end
def insert(node)
if node.word == word
increment_count(1)
elsif node.word < word
insert_into(:left, node)
else
insert_into(:right, node)
end
end
def words
self.map { |node| node.word }
end
def size
self.inject(0) { |sum, node| sum + 1 }
end
def count_all
self.inject(0) { |sum, node| sum + node.count }
end
def each
left.each {|node| yield node } unless left.nil?
yield self
right.each {|node| yield node } unless right.nil?
end
private
def increment_count(amount)
@count += amount
end
def insert_into(pos, node)
child = self.send(pos)
child ? child.insert(node) : self.send("#{pos}=", node)
end
end
end
require 'rspec'
require './binarytree'
include BinaryTree
RSpec.describe Node do
shared_examples 'Node with word "foo"' do
it "should have word equal to 'foo'" do
expect(subject.word).to eq('foo')
end
end
shared_examples 'Node with no children' do
it "should be nil on the left" do
expect(subject.left).to be_nil
end
it "should be nil on the right" do
expect(subject.right).to be_nil
end
end
shared_examples 'Node with one child with no children' do
it "should have a size of 2" do
expect(subject.size).to eq(2)
end
end
shared_examples 'Node with two children with no children' do
it "should have a size of 3" do
expect(subject.size).to eq(3)
end
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'
it "should have a size of 1" do
expect(subject.size).to eq(1)
end
it "should have a count of 1" do
expect(subject.count).to eq(1)
end
it "should have have an array of words" do
expect(subject.words).to eq(['foo'])
end
it "should have a total count of 1" do
expect(subject.count_all).to eq(1)
end
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'
it 'should be nil on the right' do
expect(subject.right).to be_nil
end
it 'should return an array of words' do
expect(subject.words).to eq(['bar', 'foo'])
end
it "should have a total count of 2" do
expect(subject.count_all).to eq(2)
end
describe 'its child on the left' do
subject { @node.left }
it_should_behave_like 'Node with no children'
it 'should have a different word' do
expect(subject.word).to eq('bar')
end
it 'should have a size of 1' do
expect(subject.size).to eq(1)
end
it 'should have a count of 1' do
expect(subject.count).to eq(1)
end
it 'should have a total count of 1' do
expect(subject.count_all).to eq(1)
end
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'
it 'should not have a left child' do
expect(subject.left).to be_nil
end
it 'should return the correct words' do
expect(subject.words).to eq(['foo', 'hoge'])
end
it 'should have a total count of 2' do
expect(subject.count_all).to eq(2)
end
describe 'its child on the right' do
subject { @node.right }
it_should_behave_like 'Node with no children'
it 'should have a different word' do
expect(subject.word).to eq('hoge')
end
it 'should have a size of 1' do
expect(subject.size).to eq(1)
end
it 'should have a count of 1' do
expect(subject.count).to eq(1)
end
it 'should have a total count of 1' do
expect(subject.count_all).to eq(1)
end
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'
it 'should have a count of 2' do
expect(subject.count).to eq(2)
end
it 'should return a single word' do
expect(subject.word).to eq('foo')
end
it 'should have a total count of 2' do
expect(subject.count_all).to eq(2)
end
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"'
it 'should not have a right child' do
expect(subject.right).to be_nil
end
it 'should have a count of 1' do
expect(subject.count).to eq(1)
end
it 'should have a size of 2' do
expect(subject.size).to eq(2)
end
it 'should return the correct words' do
expect(subject.words).to eq(['bar', 'foo'])
end
it 'should have a total count of 4' do
expect(subject.count_all).to eq(4)
end
describe 'its child on the left' do
subject { @node.left }
it 'should have the correct word' do
expect(subject.word).to eq('bar')
end
it 'should have a size of 1' do
expect(subject.size).to eq(1)
end
it 'should have a count of 3' do
expect(subject.count).to eq(3)
end
it 'should have a total count of 3' do
expect(subject.count_all).to eq(3)
end
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"'
it 'should not have a left child' do
expect(subject.left).to be_nil
end
it 'should have a count of 1' do
expect(subject.count).to eq(1)
end
it 'should have a size of 2' do
expect(subject.size).to eq(2)
end
it 'should return the correct words' do
expect(subject.words).to eq(['foo', 'hoge'])
end
it 'should have a total count of 4' do
expect(subject.count_all).to eq(4)
end
describe 'its child on the right' do
subject { @node.right }
it 'should have the correct word' do
expect(subject.word).to eq('hoge')
end
it 'should have a size of 1' do
expect(subject.size).to eq(1)
end
it 'should have a count of 3' do
expect(subject.count).to eq(3)
end
it 'should have a total count of 3' do
expect(subject.count_all).to eq(3)
end
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 }
it 'should have a size of 10' do
expect(subject.size).to eq(10)
end
it 'should return all the correct words' do
expect(subject.words).to eq(%W{a b c d e f g h i j})
end
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."
@dougjohnston
Copy link
Author

Used the specs to implement my own binary tree class.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment