23 July 2013

Algorithmathon

The goal for today is to setup the basics for trees. The basic object for trees is the node. A node is a collection of references/pointers to other nodes. Lets write the tests and code to satisfy this requirement. I will be concentrating on the BinarySearchTreeNode object. You will find a TreeNode and a BinaryTreeNode in the code on GitHub.

binary_search_tree_node_spec.rb
``````require 'spec_helper'

describe BinarySearchTreeNode do

describe "Class" do
it "should have method 'greater'" do
BinarySearchTreeNode.method_defined?(:greater).should be_true
end

it "should have method 'lesser'" do
BinarySearchTreeNode.method_defined?(:lesser).should be_true
end

it "should have method 'data'" do
BinarySearchTreeNode.method_defined?(:data).should be_true
end

it "should have method 'less_than?'" do
BinarySearchTreeNode.method_defined?(:less_than?).should be_true
end

it "should have method 'greater_than?'" do
BinarySearchTreeNode.method_defined?(:greater_than?).should be_true
end
end

describe "Instance" do

before(:each) do
@node = BinarySearchTreeNode.new(5)
end

it "should not be nil" do
@node.should_not be_nil
end

it "should not throw an exeption because greater, lesser and parent are nil" do
expect {parent = BinarySearchTreeNode.new(5)}.to_not raise_error
end

it "should throw an exeption because lesser is more than greater" do
lesser = BinarySearchTreeNode.new(10)
greater = BinarySearchTreeNode.new(5)
expect {parent = BinarySearchTreeNode.new(7,lesser,greater)}.to raise_error
end

it "should throw an exeption because lesser is not nil and greater is" do
lesser = BinarySearchTreeNode.new(10)
expect { parent = BinarySearchTreeNode.new(7,lesser) }.to raise_error
end

it "should not throw an exeption because lesser is less than greater" do
lesser = BinarySearchTreeNode.new(5)
greater = BinarySearchTreeNode.new(10)
expect {parent = BinarySearchTreeNode.new(7,lesser,greater)}.to_not raise_error
end

it "should not throw an exeption because lesser is nil and greater is not" do
greater = BinarySearchTreeNode.new(10)
expect {parent = BinarySearchTreeNode.new(7,nil,greater)}.to_not raise_error
end

it "should not throw an exeption because lesser and greater are nil" do
expect {parent = BinarySearchTreeNode.new(7)}.to_not raise_error
end

it "should throw an exeption because lesser and greater are equal" do
lesser = BinarySearchTreeNode.new(10)
greater = BinarySearchTreeNode.new(10)
expect {parent = BinarySearchTreeNode.new(7,lesser,greater)}.to raise_error
end

it "should throw an exeption because lesser and parent are equal" do
lesser = BinarySearchTreeNode.new(7)
greater = BinarySearchTreeNode.new(10)
expect {parent = BinarySearchTreeNode.new(7,lesser,greater)}.to raise_error
end

it "should throw an exeption because greater and parent are equal" do
lesser = BinarySearchTreeNode.new(3)
greater = BinarySearchTreeNode.new(7)
expect {parent = BinarySearchTreeNode.new(7,lesser,greater)}.to raise_error
end

it "should return true when lesser.lesser_than?(greater) is called" do
lesser = BinarySearchTreeNode.new(3)
greater = BinarySearchTreeNode.new(7)
lesser.less_than?(greater).should be_true
end

it "should return false when greater.greater_than?(lesser) is called" do
lesser = BinarySearchTreeNode.new(3)
greater = BinarySearchTreeNode.new(7)
greater.greater_than?(lesser).should be_true
end
end

end``````

As can be seen we have added several tests that enforce the attributes that make a Binary Search Tree. With the code below to satisfy the tests we can move on to building a Binary Search Tree.

tree_node.rb
``````class BinarySearchTreeNode
attr_accessor :lesser, :greater

def initialize(data,lesser=nil,greater=nil)
@data=data
self.lesser=lesser
self.greater=greater
if (!self.lesser.nil? && self.greater.nil?) || (!self.lesser.nil? && (self.lesser.data > self.greater.data))
throw "The lesser exceeds the greater"
end

if !self.lesser.nil? && !self.data.nil? && self.lesser.data == self.data
throw "The lesser is equal to the parent"
end

if !self.greater.nil? && !self.data.nil? && self.greater.data == self.data
throw "The greater is equal to the parent"
end

if !self.lesser.nil? && !self.greater.nil? && self.lesser.data == self.greater.data
throw "The lesser is equal to the parent"
end
end

def less_than?(target_node)
if target_node.nil?
raise "The target_node is nil!"
else
if @data < target_node.data
true
else
false
end
end
end

def greater_than?(target_node)
if target_node.nil?
raise "The target_node is nil!"
else
if @data > target_node.data
true
else
false
end
end
end
end``````

What do we know about a binary search tree? We know that it needs a starting node know as the "root". If we are going to be able to write algorithms against a tree we need to be able to build a tree. This means we need a "root" attribute and an "add" method. We should add several tests to specify the functionality we need. These tests come quite naturally if you use the Test Driven Development methodology.

binary_search_tree_spec.rb
``````require 'spec_helper'

describe BinarySearchTree do

describe "Class" do
it "should have method 'root'" do
BinarySearchTree.method_defined?(:root).should be_true
end

it "should have method 'add'" do
end
end

describe "Instance" do

before(:each) do
@tree = BinarySearchTree.new()
end

it "should have node(5) as the root when passed into constructor" do
node = BinarySearchTreeNode.new(5)
tree = BinarySearchTree.new(node)
tree.root.should_not be_nil
tree.root.data.should == 5
end

it "should have node(6) as the root when add(node(5)) is called" do
node = BinarySearchTreeNode.new(5)
tree = BinarySearchTree.new()
tree.root.should_not be_nil
tree.root.data.should == 5
end

it "should have add(node(5)) as the lesser of the root" do
node = BinarySearchTreeNode.new(5)
tree = BinarySearchTree.new(BinarySearchTreeNode.new(10))
tree.root.lesser.should_not be_nil
tree.root.lesser.data.should == 5
end

it "should have add(node(15)) as the greater of the root" do
node = BinarySearchTreeNode.new(15)
tree = BinarySearchTree.new(BinarySearchTreeNode.new(10))
tree.root.greater.should_not be_nil
tree.root.greater.data.should == 15
end

it "should have add(node(10)) raise an error" do
node = BinarySearchTreeNode.new(10)
tree = BinarySearchTree.new(BinarySearchTreeNode.new(10))
end

it "should have add(node(50)) as the lesser of the root.lesser" do
node1 = BinarySearchTreeNode.new(75)
node2 = BinarySearchTreeNode.new(50)
tree = BinarySearchTree.new(BinarySearchTreeNode.new(100))
tree.root.lesser.should_not be_nil
tree.root.lesser.lesser.should_not be_nil
tree.root.lesser.lesser.data.should == 50
end

it "should have add(node(85)) as the greater of the root.lesser" do
node1 = BinarySearchTreeNode.new(75)
node2 = BinarySearchTreeNode.new(85)
tree = BinarySearchTree.new(BinarySearchTreeNode.new(100))
tree.root.lesser.should_not be_nil
tree.root.lesser.greater.should_not be_nil
tree.root.lesser.greater.data.should == 85
end

it "should have add(node(150)) as the greater of the root" do
node1 = BinarySearchTreeNode.new(150)
tree = BinarySearchTree.new(BinarySearchTreeNode.new(100))
tree.root.greater.should_not be_nil
tree.root.greater.data.should == 150
end

it "should return 125 when it recieves the root.greater.lesser.data call" do
node1 = BinarySearchTreeNode.new(150)
node2 = BinarySearchTreeNode.new(75)
node3 = BinarySearchTreeNode.new(125)
tree = BinarySearchTree.new(BinarySearchTreeNode.new(100))
tree.root.greater.should_not be_nil
tree.root.greater.lesser.should_not be_nil
tree.root.greater.lesser.data.should == 125
end

end

end``````
binary_search_tree.rb
``````class BinarySearchTree

def initialize(root=nil)
@root=root
end

if new_node.nil?
new_node
else
if @root.nil?
@root = new_node
else
end
end
end

private

if current_node.nil?
current_node
else
if current_node.greater_than?(new_node)
if current_node.lesser.nil?
current_node.lesser=new_node
else
end
elsif current_node.less_than?(new_node)
if current_node.greater.nil?
current_node.greater=new_node
else