Akbar Binary Tree November 16th, 2007
Binary tree is important topic in computer science, especially in data structures field. The important characteristics are fast insertion, retrieving sorted data rapidly. Binary tree can be described like this. Every node has two leaves nodes. One or both of these two leaves nodes maybe be empty or using computer science terminology, null. Some people like to call these two leaves nodes as children nodes. Every binary tree has one root node. So there is no ambiguity for choosing starting point. After that you will have two choices every time you want to continue your journey traveling down the tree, except when the child leaf is empty or null.
We can use binary tree as efficient data structures for sorted data. When sorted data is implemented with binary tree data structures, we can rapidly store sorted data and rapidly retrieve sorted data. If you learn C/C++ and Pascal, most likely you will encounter lesson sorting data using binary tree. In C/C++ the node is implemented with struct with three fields. The first will be holder for value/data. The second and third will be pointer to this struct type data. In Ruby you can use Struct or Class as node. You don’t have pointer in Ruby but you use object reference as replacement. Most likely you will not use binary tree as data structures for sorted data in Ruby. But there are some cases that make binary tree suitable for data structures in Ruby.
One of case that makes binary tree useful is this quiz. Binary tree is suitable data structure for database in this quiz. You put questions in interior nodes and another questions or the answers in children nodes. Using object reference give a little headache when solving this quiz. In the code given later in this post, if you remove the clone method from leaf object, it will screw up. Because if you don’t use clone method, the reference in other leaves nodes maybe lost when you update the relevant leaf node.
Tree means recursive function. The recursive function in my code for the quiz is play. When you choose ‘no’ for the answer, it will call function play with leaf.no. When you choose ‘yes’ for the answer, it will call function play with leaf.yes.
There is other way to implement binary tree beside using struct like type. Using array. There is rule for finding children or parent for specific index. For index i, its children are 2i + 1 and 2i + 2. For index i, its parent is (i – 1) / 2. But it is more complicated than using struct type data.
So here is the code:
# solve ruby quiz # 15 http://www.rubyquiz.com/quiz15.html
# our struct
Animal = Struct.new(:que_name, :yes, :no)
# in the beginning, there is only elephant
elephant = Animal.new('an elephant', nil, nil)
@root = Animal.new('is it an elephant?', elephant, nil)
@direction_leaf = nil
@before_leaf = nil
def ask
gets.chomp.downcase
end
def yes?(answer)
if answer == 'yes' || answer == 'y' then
return true
else
return false
end
end
# our playing session
def play( leaf )
# check if we are in very leaf node
if leaf.yes.nil? then
puts 'I win. Pretty smart, aren\'t I?'
if ask_play_again then
puts 'Think of an animal...'
play @root
end
else
puts leaf.que_name + ' (y or n)'
answer = ask
if yes?(answer) then
@before_leaf = leaf
@direction_leaf = 'yes'
play leaf.yes
else
if leaf.no.nil? then
add_information leaf
if ask_play_again then
puts 'Think of an animal...'
play @root
end
else
@direction_leaf = 'no'
@before_leaf = leaf
play leaf.no
end
end
end
end
def add_information(leaf)
puts 'You win. Help me learn from mistake before you go...'
puts 'What animal were you thinking of?'
new_animal = ask
puts 'Give me a question to distinguish ' + new_animal + ' from ' + leaf.yes.que_name + '.'
new_question = ask
puts 'For ' + new_animal + ', what is the answer to your question? (y or n)'
new_answer = ask
# created other leaf
new_upper_question = Animal.new(new_question, nil, nil)
new_animal_leaf = Animal.new(new_animal, nil, nil)
new_middle_question = Animal.new('Is it ' + new_animal + '?', new_animal_leaf, nil)
if yes?(new_answer) then
new_upper_question.no = leaf.clone
new_upper_question.yes = new_middle_question
else
new_upper_question.yes = leaf.clone
new_upper_question.no = new_middle_question
end
if @before_leaf then
if @direction_leaf == 'yes' then
@before_leaf.yes = new_upper_question
else
@before_leaf.no = new_upper_question
end
else
@root = new_upper_question
end
a = 1
end
def ask_play_again
puts 'Play again? (y or n)'
play_again = ask
yes?(play_again) ? true : false
end
# play the game
play @root