Binary Tree

[Martin]

Hi all!

I'm a newbie in Ruby and I am trying to implement a Binary Tree.
However, it doesn't work. Could someone please help me?

Thank you !

class Node
attr_accessor :left, :right, :key, :data

def initialize(key, data)
@left = nil
@right = nil
@key = key
@data = data
end

def to_s()
print "Key = ", @key, " Data = ", @data
end
end

class Tree
attr_accessor :root

public
def initialize()
@root = nil
print "Root Object Id ", @root.object_id, "\n"
end

def insert(newNode)
insertNode(@root, newNode)
end

def visit()
visitNode(@root)
end

private
def insertNode(node, newNode)
print "Node Object Id ", node.object_id, "\n"
print "New Node Object Id ", newNode.object_id, "\n"
if (node == nil)
node = newNode
print "Node Affected Object Id ", node.object_id, "\n"
print @root
print node
else
if (newNode.data <= node.data)
insertNode(node.left, newNode)
print "Gauche"
else
insertNode(node.right, newNode)
print "Droite"
end
end
end

def visitNode(node)
if (node != nil)
print node.key

if (node.left != nil)
visitNode(node.left)
end

if (node.right != nil)
visitNode(node.right )
end
end
end
end


arbre = Tree.new
arbre.insert(Node.new(1, "un"))
arbre.insert(Node.new(2, "deux"))
arbre.insert(Node.new(3, "trois"))

arbre.visit()

 

[Dan Zwell]

Hi all!

I'm a newbie in Ruby and I am trying to implement a Binary Tree.
However, it doesn't work. Could someone please help me?

Thank you !

class Node
attr_accessor :left, :right, :key, :data

def initialize(key, data)
@left = nil
@right = nil
@key = key
@data = data
end

def to_s()
print "Key = ", @key, " Data = ", @data
end
end

class Tree
attr_accessor :root

public
def initialize()
@root = nil
print "Root Object Id ", @root.object_id, "\n"
end

def insert(newNode)
insertNode(@root, newNode)
end

def visit()
visitNode(@root)
end

private
def insertNode(node, newNode)
print "Node Object Id ", node.object_id, "\n"
print "New Node Object Id ", newNode.object_id, "\n"
if (node == nil)
node = newNode
print "Node Affected Object Id ", node.object_id, "\n"
print @root
print node
else
if (newNode.data <= node.data)
insertNode(node.left, newNode)
print "Gauche"
else
insertNode(node.right, newNode)
print "Droite"
end
end
end

def visitNode(node)
if (node != nil)
print node.key

if (node.left != nil)
visitNode(node.left)
end

if (node.right != nil)
visitNode(node.right )
end
end
end
end


arbre = Tree.new
arbre.insert(Node.new(1, "un"))
arbre.insert(Node.new(2, "deux"))
arbre.insert(Node.new(3, "trois"))

arbre.visit()

Martin,

In short, I don't know how to fix it. But the problem is with this line:

node = newNode

It doesn't seem to do what you want. I think it takes the reference
variable "node" (previously pointing at @root, until the method
recurses) and point it at a new variable ("newNode"). That isn't what
you want--you want to replace the contents of the node, not change the
reference. I don't know how to do this. I got something by changing the
above line to "@root = newNode", but that really breaks the algorithm.

Dan Zwell

 

[martingagne]

Martin,

In short, I don't know how to fix it. But the problem is with this line:

node = newNode

It doesn't seem to do what you want. I think it takes the reference
variable "node" (previously pointing at @root, until the method
recurses) and point it at a new variable ("newNode"). That isn't what
you want--you want to replace the contents of the node, not change the
reference. I don't know how to do this. I got something by changing the
above line to "@root = newNode", but that really breaks the algorithm.

Dan Zwell

Hi Dan,

You're right, the problematic line is definitely: node = newNode.

When the tree has no root (@root == nil), the first node added to the
tree should become the root. That's why I check just before if the
node is nil. Since this method is called by insert which pass to
insertNode the class attribute @root, why Ruby doesn't change the
value of @root for the value of newNode. I thought that Ruby was using
only references... Am I right?

Thank you for your help...

Martin

 

[Dan Zwell]

Hi Dan,

You're right, the problematic line is definitely: node = newNode.

When the tree has no root (@root == nil), the first node added to the
tree should become the root. That's why I check just before if the
node is nil. Since this method is called by insert which pass to
insertNode the class attribute @root, why Ruby doesn't change the
value of @root for the value of newNode. I thought that Ruby was using
only references... Am I right?

Thank you for your help...

Martin

Ruby doesn't change the value of @root (even though that is what is
pointed to by "node") because it's busy changing the value of "node".
Ruby variables don't seem to mate for life. As soon as ruby sees the
'=', "node" no longer points at @root. This may be one disadvantage of a
really loosely typed language. As for how to make the binary tree work,
I can't think of a way that doesn't involve rewriting a lot of it to
avoid this problem. If you really wanted to, perhaps you could store the
nodes in an array and pass around index numbers instead of passing
around nodes themselves? But then you lose some of advantages of a
binary tree, and it's really not elegant.

You could rewrite the algorithm a little, but it is going to involve two
things:
- at some point, you will need to explicitly set @root
- I suspect "node.left =" and "node.right =" will work as expected, so
you wan assign to those directly, even if "node" is just some variable.

Sorry for not having a good answer,

Dan

 

[nash e. foster]

I think this is more complex than necessary. I'll go through yours
and then show you another approach. Your tree is a little weird,
though, as it doesn't sort or balance anything. That's not wrong,
just unusual.

class Node
attr_accessor :left, :right, :key, :data

def initialize(key, data)

Best to provide a default for key and data. E.g.,

def initialize(key="root", data=0)

@left = nil
@right = nil
@key = key
@data = data
end

def to_s()
print "Key = ", @key, " Data = ", @data

More idiomatic ruby:

p "Key = #{@key} Data = #{@data}"

end
end

class Tree

The Tree class isn't really helpful here. Having a higher level
object to contain the nodes isn't bad or wrong, but it complicates
things and it's distracting. My implementation below just omitted
this, but you could put it back. Putting the logic in the Tree class
is actually probably better, since individual Node instances could
be part of multiple Trees with different logic all at the same time,
but we're getting ahead of ourselves.

private
def insertNode(node, newNode)
print "Node Object Id ", node.object_id, "\n"
print "New Node Object Id ", newNode.object_id, "\n"
if (node == nil)
node = newNode

The variable 'node' is an argument variable. It's basically like a
stack variable in C. When insertNode returns, the binding goes away
and so this assignment only does something within the context of this
function. The variable "node" doesn't hold a reference to the original
variable's slot from the calling function. Here's another example:

def foo()
x = 1
bar(x)
p x
end

def bar(y)
y = 5
p y
end

foo()
5
1

See? When bar is done, the 'y' variable goes away and the value '5' is
lost. It's not stored in the place the original 'x' lived because they
are different variables.

print "Node Affected Object Id ", node.object_id, "\n"
print @root
print node
else
if (newNode.data <= node.data)
insertNode(node.left, newNode)
print "Gauche"
else
insertNode(node.right, newNode)
print "Droite"
end
end
end

def visitNode(node)
if (node != nil)
print node.key

if (node.left != nil)
visitNode(node.left)
end

if (node.right != nil)
visitNode(node.right )
end
end
end
end


arbre = Tree.new
arbre.insert(Node.new(1, "un"))
arbre.insert(Node.new(2, "deux"))
arbre.insert(Node.new(3, "trois"))

arbre.visit()

Ok, here's mine:

class Node
attr_accessor :left, :right, :key, :data

def initialize(key="root", data=0)
@left = nil
@right = nil
@key = key
@data = data
end

def insert(newNode)
return if nil == newNode

# insert it to the left if it's <= what we have, otherwise right
if self.data <= newNode.data then
if @left then
@left.insert newNode
else
@left = newNode
end
else
if @right then
@right.insert newNode
else
@right = newNode
end
end
end

def visit(depth=0)
print " " * depth * 2 # two spaces per level in the tree
print "#{self.key} -> #{self.data}\n"
@left.visit(depth+1) if @left
@right.visit(depth+1) if @right
end
end

arbre = Node.new
arbre.insert Node.new("un", 1)
arbre.insert Node.new("quatre", -4)
arbre.insert Node.new("deux", 2)
arbre.insert Node.new("trois", 3)

arbre.visit


ciao,


--nash

 

[Jan Friedrich]

I'm a newbie in Ruby and I am trying to implement a Binary Tree.
<snip>
def to_s()
print "Key = ", @key, " Data = ", @data
end
end

btw: The method to_s should *return* a string *not print* a string!

def to_s
"Key = #@key Data = #@data"
end


regards
Jan