Binary Tree

Discussion in 'Ruby' started by Martin, Apr 21, 2007.

  1. Martin

    Martin Guest

    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()

    --
    Posted via http://www.ruby-forum.com/.
     
    Martin, Apr 21, 2007
    #1
    1. Advertising

  2. Martin

    Dan Zwell Guest

    Martin wrote:
    > 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
     
    Dan Zwell, Apr 21, 2007
    #2
    1. Advertising

  3. Martin

    Guest

    On Apr 21, 12:26 am, Dan Zwell <> wrote:
    > Martin wrote:
    > > 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


    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
     
    , Apr 21, 2007
    #3
  4. Martin

    Dan Zwell Guest

    wrote:
    > On Apr 21, 12:26 am, Dan Zwell <> wrote:
    >> Martin wrote:
    >>> 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

    >
    > 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
     
    Dan Zwell, Apr 21, 2007
    #4
  5. 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.

    On Sat, Apr 21, 2007 at 11:28:41AM +0900, Martin wrote:
    >
    > 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
     
    nash e. foster, Apr 21, 2007
    #5
  6. Martin wrote:
    > 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
     
    Jan Friedrich, Apr 21, 2007
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,203
  2. sharan
    Replies:
    4
    Views:
    705
    CBFalconer
    Oct 30, 2007
  3. sharan
    Replies:
    2
    Views:
    859
    SM Ryan
    Oct 31, 2007
  4. sharan
    Replies:
    1
    Views:
    708
    CBFalconer
    Oct 30, 2007
  5. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,202
    Michael Angelo Ravera
    Oct 21, 2010
Loading...

Share This Page