Tree structure - how do we link nodes together?

Discussion in 'Ruby' started by Aldric Giacomoni, Feb 18, 2009.

  1. I know I could just use rubytree, which looks quite nice, but I'd like
    to see what you guys would do about creating a tree and linking the
    nodes together.
    In C++ we'd just make pointers, so how would we do the equivalent in Ruby?

    --Aldric
     
    Aldric Giacomoni, Feb 18, 2009
    #1
    1. Advertising

  2. Aldric Giacomoni

    Dylan Evans Guest

    [Note: parts of this message were removed to make it a legal post.]

    I would be inclined to use an array, part of the beauty of dynamic languages
    is the typeless nature of arrays which does away with a lot of management
    code, in c++ trees i normally write a base node class then branch and leaf
    nodes which is a lot of work compared to [x, [y, z]]
    Of course if you wanted to create branch nodes for some custom purpose then
    you could just assign the children to it since they are passed by reference.

    On Wed, Feb 18, 2009 at 11:30 AM, Aldric Giacomoni <"aldric[removeme]"@
    trevoke.net> wrote:

    > I know I could just use rubytree, which looks quite nice, but I'd like
    > to see what you guys would do about creating a tree and linking the
    > nodes together.
    > In C++ we'd just make pointers, so how would we do the equivalent in Ruby?
    >
    > --Aldric
    >
    >



    --
    The UNIX system has a command, nice ... in order to be nice to the other
    users. Nobody ever uses it." - Andrew S. Tanenbaum
     
    Dylan Evans, Feb 18, 2009
    #2
    1. Advertising

  3. 2009/2/18 Aldric Giacomoni <"aldric[removeme]"@trevoke.net>:
    > I know I could just use rubytree, which looks quite nice, but I'd like
    > to see what you guys would do about creating a tree and linking the
    > nodes together.
    > In C++ we'd just make pointers, so how would we do the equivalent in Ruby?


    We use object references - as always when referring other objects.
    Ruby does not have the multitude of options that C++ has.

    Cheers

    robert


    --
    remember.guy do |as, often| as.you_can - without end
     
    Robert Klemme, Feb 18, 2009
    #3
  4. Robert Klemme wrote:
    > 2009/2/18 Aldric Giacomoni <"aldric[removeme]"@trevoke.net>:
    >
    >> I know I could just use rubytree, which looks quite nice, but I'd like
    >> to see what you guys would do about creating a tree and linking the
    >> nodes together.
    >> In C++ we'd just make pointers, so how would we do the equivalent in Ruby?
    >>

    >
    > We use object references - as always when referring other objects.
    > Ruby does not have the multitude of options that C++ has.
    >
    > Cheers
    >
    > robert
    >
    >
    >

    Alright, Robert - I don't know how that works in Ruby! Would you provide
    me with a simple example, explain it, or point me to something that
    explains it, please?

    Thanks,

    --Aldric
     
    Aldric Giacomoni, Feb 18, 2009
    #4
  5. Dylan Evans wrote:
    > [Note: parts of this message were removed to make it a legal post.]
    >
    > I would be inclined to use an array, part of the beauty of dynamic languages
    > is the typeless nature of arrays which does away with a lot of management
    > code, in c++ trees i normally write a base node class then branch and leaf
    > nodes which is a lot of work compared to [x, [y, z]]
    > Of course if you wanted to create branch nodes for some custom purpose then
    > you could just assign the children to it since they are passed by reference.
    >
    >

    How would .. passing the children by reference work? Is that the same
    thing that Robert is talking about?
    The idea of an array is simple enough that it might work.. I should be
    able to write something to handle however many layers deep the arrays
    go.. But I think a tree may be a little handier to handle things like
    deleting a node and its children.
    --Aldric
     
    Aldric Giacomoni, Feb 18, 2009
    #5
  6. Aldric Giacomoni

    Glen Holcomb Guest

    [Note: parts of this message were removed to make it a legal post.]

    On Wed, Feb 18, 2009 at 7:20 AM, Aldric Giacomoni <"aldric[removeme]"@
    trevoke.net> wrote:

    > Robert Klemme wrote:
    > > 2009/2/18 Aldric Giacomoni <"aldric[removeme]"@trevoke.net>:
    > >
    > >> I know I could just use rubytree, which looks quite nice, but I'd like
    > >> to see what you guys would do about creating a tree and linking the
    > >> nodes together.
    > >> In C++ we'd just make pointers, so how would we do the equivalent in

    > Ruby?
    > >>

    > >
    > > We use object references - as always when referring other objects.
    > > Ruby does not have the multitude of options that C++ has.
    > >
    > > Cheers
    > >
    > > robert
    > >
    > >
    > >

    > Alright, Robert - I don't know how that works in Ruby! Would you provide
    > me with a simple example, explain it, or point me to something that
    > explains it, please?
    >
    > Thanks,
    >
    > --Aldric
    >
    >

    Pretty Simple really:

    class Node
    attr_accessor :data
    attr_accessor :left
    attr_accessor :right
    end

    root = Node.new

    node1 = Node.new

    root.data = "rob"
    node1.data = "tim"
    root.right = node1
     
    Glen Holcomb, Feb 18, 2009
    #6
  7. [Note: parts of this message were removed to make it a legal post.]

    On Wed, Feb 18, 2009 at 9:29 AM, Aldric Giacomoni <"aldric[removeme]"@
    trevoke.net> wrote:

    > Dylan Evans wrote:
    > > [Note: parts of this message were removed to make it a legal post.]
    > >
    > > I would be inclined to use an array, part of the beauty of dynamic

    > languages
    > > is the typeless nature of arrays which does away with a lot of management
    > > code, in c++ trees i normally write a base node class then branch and

    > leaf
    > > nodes which is a lot of work compared to [x, [y, z]]
    > > Of course if you wanted to create branch nodes for some custom purpose

    > then
    > > you could just assign the children to it since they are passed by

    > reference.
    > >
    > >

    > How would .. passing the children by reference work?



    Ruby is a uniformly object oriented language, all values are object
    references. Variables, and parameters are simply named references to
    objects, not the objects themselves. Individual slots in an array also hold
    reverences to objects rather than the objects themselves, they just don't
    have names.

    So everything is passed by object reference. This is not the same thing as
    passing by referernce in a language like C, although the differences can be
    subtle.

    Here's an oldie but goody of mine which might help understand the
    relationship between variables, values, and objects.

    http://talklikeaduck.denhaven2.com/articles/2006/09/13/on-variables-values-and-objects


    --
    Rick DeNatale

    Blog: http://talklikeaduck.denhaven2.com/
    Twitter: http://twitter.com/RickDeNatale
     
    Rick DeNatale, Feb 18, 2009
    #7
  8. On 18.02.2009 15:18, Aldric Giacomoni wrote:
    > Robert Klemme wrote:
    >> 2009/2/18 Aldric Giacomoni <"aldric[removeme]"@trevoke.net>:
    >>
    >>> I know I could just use rubytree, which looks quite nice, but I'd like
    >>> to see what you guys would do about creating a tree and linking the
    >>> nodes together.
    >>> In C++ we'd just make pointers, so how would we do the equivalent in Ruby?
    >>>

    >> We use object references - as always when referring other objects.
    >> Ruby does not have the multitude of options that C++ has.


    > Alright, Robert - I don't know how that works in Ruby! Would you provide
    > me with a simple example, explain it, or point me to something that
    > explains it, please?


    I wasn't aware that you were after _such_ basic information. Actually,
    since you mentioned using rubytree I assumed that you are familiar with
    the language. The simplest and most basic form of a relation between
    two objects is probably:

    class Foo
    def set(x)
    @the_other = x
    end
    end

    f = Foo.new
    x = Foo.new
    f.set(x)

    Now f references x.

    I suggest you get your hands on David's new book once it is out and in
    the meantime consult those various introductory documents (can be found
    via http://www.ruby-doc.org/).

    Cheers

    robert
     
    Robert Klemme, Feb 18, 2009
    #8
  9. Robert Klemme wrote:
    > On 18.02.2009 15:18, Aldric Giacomoni wrote:
    >> Robert Klemme wrote:
    >>> 2009/2/18 Aldric Giacomoni <"aldric[removeme]"@trevoke.net>:
    >>>
    >>>> I know I could just use rubytree, which looks quite nice, but I'd like
    >>>> to see what you guys would do about creating a tree and linking the
    >>>> nodes together.
    >>>> In C++ we'd just make pointers, so how would we do the equivalent
    >>>> in Ruby?
    >>>>
    >>> We use object references - as always when referring other objects.
    >>> Ruby does not have the multitude of options that C++ has.

    >
    >> Alright, Robert - I don't know how that works in Ruby! Would you provide
    >> me with a simple example, explain it, or point me to something that
    >> explains it, please?

    >
    > I wasn't aware that you were after _such_ basic information.
    > Actually, since you mentioned using rubytree I assumed that you are
    > familiar with the language. The simplest and most basic form of a
    > relation between two objects is probably:
    >
    > class Foo
    > def set(x)
    > @the_other = x
    > end
    > end
    >
    > f = Foo.new
    > x = Foo.new
    > f.set(x)
    >
    > Now f references x.
    >
    > I suggest you get your hands on David's new book once it is out and in
    > the meantime consult those various introductory documents (can be
    > found via http://www.ruby-doc.org/).
    >
    > Cheers
    >
    > robert
    >

    Essentially, the main information you require is that, everything in
    Ruby is an object, and every object is actually a reference to an object.

    so
    class Foo

    attr_reader :the_other

    def set(x)
    @the_other = x
    end
    end

    f = Foo.new
    bar = f
    bar.the_other => nil
    x = Foo.new
    f.set(x)
    bar.the_other => x

    It helps me to think of references and the objects they point to as
    separate entities (I'm unsure of the truthfulness of this). It's the
    opposite of c++ really. c++ requires you to explicitly state you want
    pass-by-reference and Ruby requires you to state pass-by-value (which
    ends up in the form of a .dup call all the times I've ever wanted to use
    it, which is less often than you might think)

    Cheers,
    Michael

    =======================================================================
    This email, including any attachments, is only for the intended
    addressee. It is subject to copyright, is confidential and may be
    the subject of legal or other privilege, none of which is waived or
    lost by reason of this transmission.
    If the receiver is not the intended addressee, please accept our
    apologies, notify us by return, delete all copies and perform no
    other act on the email.
    Unfortunately, we cannot warrant that the email has not been
    altered or corrupted during transmission.
    =======================================================================
     
    Michael Malone, Feb 18, 2009
    #9
  10. [Note: parts of this message were removed to make it a legal post.]

    On Wed, Feb 18, 2009 at 5:08 PM, Michael Malone
    <>wrote:

    > Essentially, the main information you require is that, everything in Ruby
    > is an object, and every object is actually a reference to an object.
    >


    Actually, no.

    The value of any expression is an object.

    Every object consists of references to objects.

    Variables and parameters are named references to objects.

    Assignment transfers the reference to the object, not the object itself.

    --
    Rick DeNatale

    Blog: http://talklikeaduck.denhaven2.com/
    Twitter: http://twitter.com/RickDeNatale
    WWR: http://www.workingwithrails.com/person/9021-rick-denatale
    LinkedIn: http://www.linkedin.com/in/rickdenatale
     
    Rick DeNatale, Feb 18, 2009
    #10
  11. Aldric Giacomoni

    Gary Wright Guest

    On Feb 18, 2009, at 5:33 PM, Rick DeNatale wrote:
    > Actually, no.
    >
    > The value of any expression is an object.


    I thought you were pretty clear in

    <http://talklikeaduck.denhaven2.com/articles/2006/09/13/on-variables-values-and-objects
    >


    that values in Ruby are references, not objects. That
    posting is one of the nicest expositions on Ruby's object
    model that I've seen.

    It took me quite a while to get a good mental picture of
    Ruby's object model. Part of the problem was that the
    community doesn't (or didn't) seem to have a consensus
    on terminology in this area. Discussions about values,
    references, expressions, objects, assignment semantics,
    immutable types, symbols, identity,
    and so on often resemble a druken sailor's random walk
    rather than an simple, easily followed narrative.
     
    Gary Wright, Feb 18, 2009
    #11
  12. Aldric Giacomoni

    Ken Bloom Guest

    On Tue, 17 Feb 2009 20:25:28 -0500, Aldric Giacomoni wrote:

    > I know I could just use rubytree, which looks quite nice, but I'd like
    > to see what you guys would do about creating a tree and linking the
    > nodes together.
    > In C++ we'd just make pointers, so how would we do the equivalent in
    > Ruby?


    The easiest equivalence is that essentially everything in Ruby is a
    pointer and the . operator in Ruby is the equivalent of C++'s -> (This is
    similar to how Java behaves as well.) The = operator changes where the
    pointer points.

    There's no such thing in Ruby as a pointer to a pointer, nor is there any
    such thing as a variable that's not a pointer at all.

    --Ken

    --
    Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
    Department of Computer Science. Illinois Institute of Technology.
    http://www.iit.edu/~kbloom1/
     
    Ken Bloom, Feb 19, 2009
    #12
  13. On 18.02.2009 23:48, Gary Wright wrote:
    > On Feb 18, 2009, at 5:33 PM, Rick DeNatale wrote:
    >> Actually, no.
    >>
    >> The value of any expression is an object.

    >
    > I thought you were pretty clear in
    >
    > <http://talklikeaduck.denhaven2.com/articles/2006/09/13/on-variables-values-and-objects
    > >

    >
    > that values in Ruby are references, not objects. That
    > posting is one of the nicest expositions on Ruby's object
    > model that I've seen.


    Well, there are several valid notions of "value" in the domain of
    programming languages and it partly depends on the context which one you
    choose. You could identify these

    1. value, technical

    These are the the "things" that you really see, i.e. object references.
    This is the only thing you'll ever get to see from an object. These
    are also the values meant when talking about call semantics (call by value).

    2. values, practical

    From a practical point of view much more important are objects because
    those are the things that really carry state in Ruby. Whenever you
    reason about a program and what it should do (or try to find out what it
    does) you do this in terms of the objects living in the program -
    although you never see one. :)

    > It took me quite a while to get a good mental picture of
    > Ruby's object model. Part of the problem was that the
    > community doesn't (or didn't) seem to have a consensus
    > on terminology in this area. Discussions about values,
    > references, expressions, objects, assignment semantics,
    > immutable types, symbols, identity,
    > and so on often resemble a druken sailor's random walk
    > rather than an simple, easily followed narrative.


    Nevertheless, the drunken sailor pretty often reaches the harbour. :)

    Kind regards

    robert

    --
    remember.guy do |as, often| as.you_can - without end
     
    Robert Klemme, Feb 19, 2009
    #13
  14. Aldric Giacomoni

    Dylan Evans Guest

    [Note: parts of this message were removed to make it a legal post.]

    On Thu, Feb 19, 2009 at 12:29 AM, Aldric Giacomoni <"aldric[removeme]"@
    trevoke.net> wrote:

    > Dylan Evans wrote:
    > > [Note: parts of this message were removed to make it a legal post.]
    > >
    > > I would be inclined to use an array, part of the beauty of dynamic

    > languages
    > > is the typeless nature of arrays which does away with a lot of management
    > > code, in c++ trees i normally write a base node class then branch and

    > leaf
    > > nodes which is a lot of work compared to [x, [y, z]]
    > > Of course if you wanted to create branch nodes for some custom purpose

    > then
    > > you could just assign the children to it since they are passed by

    > reference.
    > >
    > >

    > How would .. passing the children by reference work? Is that the same
    > thing that Robert is talking about?
    > The idea of an array is simple enough that it might work.. I should be
    > able to write something to handle however many layers deep the arrays



    It's fairly common in the c/c++ world to implement tree's with arrays, a
    matter of preference really, or in some cases it may be quicker to access a
    node by it's index rather than searching through a linked list, or a pain
    reallocating memory. Of course i don't know what your planning so i'm just
    guessing, but you should be able to search with a recursive function. You
    may also find a hash more convenient for accessing child nodes.

    >
    > go.. But I think a tree may be a little handier to handle things like
    > deleting a node and its children.



    Check out Array#delete<http://www.ruby-doc.org/core/classes/Array.html#M002216>


    >
    > --Aldric
    >
    >



    --
    The UNIX system has a command, nice ... in order to be nice to the other
    users. Nobody ever uses it." - Andrew S. Tanenbaum
     
    Dylan Evans, Feb 19, 2009
    #14
  15. Glen Holcomb wrote:
    > [Note: parts of this message were removed to make it a legal post.]
    >
    > On Wed, Feb 18, 2009 at 7:20 AM, Aldric Giacomoni <"aldric[removeme]"@
    > trevoke.net> wrote:
    >
    >
    >> Robert Klemme wrote:
    >>
    >>> 2009/2/18 Aldric Giacomoni <"aldric[removeme]"@trevoke.net>:
    >>>
    >>>
    >>>> I know I could just use rubytree, which looks quite nice, but I'd like
    >>>> to see what you guys would do about creating a tree and linking the
    >>>> nodes together.
    >>>> In C++ we'd just make pointers, so how would we do the equivalent in
    >>>>

    >> Ruby?
    >>
    >>> We use object references - as always when referring other objects.
    >>> Ruby does not have the multitude of options that C++ has.
    >>>
    >>> Cheers
    >>>
    >>> robert
    >>>
    >>>
    >>>
    >>>

    >> Alright, Robert - I don't know how that works in Ruby! Would you provide
    >> me with a simple example, explain it, or point me to something that
    >> explains it, please?
    >>
    >> Thanks,
    >>
    >> --Aldric
    >>
    >>
    >>

    > Pretty Simple really:
    >
    > class Node
    > attr_accessor :data
    > attr_accessor :left
    > attr_accessor :right
    > end
    >
    > root = Node.new
    >
    > node1 = Node.new
    >
    > root.data = "rob"
    > node1.data = "tim"
    > root.right = node1
    >
    >

    Oh - DUH !
    Thanks. Clearly I wasn't thinking straight.
    --Aldric
     
    Aldric Giacomoni, Feb 19, 2009
    #15
  16. Rick DeNatale wrote:
    > [Note: parts of this message were removed to make it a legal post.]
    >
    > On Wed, Feb 18, 2009 at 9:29 AM, Aldric Giacomoni <"aldric[removeme]"@
    > trevoke.net> wrote:
    >
    >
    >> Dylan Evans wrote:
    >>
    >>> [Note: parts of this message were removed to make it a legal post.]
    >>>
    >>> I would be inclined to use an array, part of the beauty of dynamic
    >>>

    >> languages
    >>
    >>> is the typeless nature of arrays which does away with a lot of management
    >>> code, in c++ trees i normally write a base node class then branch and
    >>>

    >> leaf
    >>
    >>> nodes which is a lot of work compared to [x, [y, z]]
    >>> Of course if you wanted to create branch nodes for some custom purpose
    >>>

    >> then
    >>
    >>> you could just assign the children to it since they are passed by
    >>>

    >> reference.
    >>
    >>>

    >> How would .. passing the children by reference work?
    >>

    >
    >
    > Ruby is a uniformly object oriented language, all values are object
    > references. Variables, and parameters are simply named references to
    > objects, not the objects themselves. Individual slots in an array also hold
    > reverences to objects rather than the objects themselves, they just don't
    > have names.
    >
    > So everything is passed by object reference. This is not the same thing as
    > passing by referernce in a language like C, although the differences can be
    > subtle.
    >
    > Here's an oldie but goody of mine which might help understand the
    > relationship between variables, values, and objects.
    >
    > http://talklikeaduck.denhaven2.com/articles/2006/09/13/on-variables-values-and-objects
    >
    >
    >

    Great little post.. Thanks, I'd forgotten some of the basics :)
     
    Aldric Giacomoni, Feb 19, 2009
    #16
  17. Robert Klemme wrote:
    > On 18.02.2009 15:18, Aldric Giacomoni wrote:
    >> Robert Klemme wrote:
    >>> 2009/2/18 Aldric Giacomoni <"aldric[removeme]"@trevoke.net>:
    >>>
    >>>> I know I could just use rubytree, which looks quite nice, but I'd like
    >>>> to see what you guys would do about creating a tree and linking the
    >>>> nodes together.
    >>>> In C++ we'd just make pointers, so how would we do the equivalent
    >>>> in Ruby?
    >>>>
    >>> We use object references - as always when referring other objects.
    >>> Ruby does not have the multitude of options that C++ has.

    >
    >> Alright, Robert - I don't know how that works in Ruby! Would you provide
    >> me with a simple example, explain it, or point me to something that
    >> explains it, please?

    >
    > I wasn't aware that you were after _such_ basic information.
    > Actually, since you mentioned using rubytree I assumed that you are
    > familiar with the language. The simplest and most basic form of a
    > relation between two objects is probably:
    >
    > class Foo
    > def set(x)
    > @the_other = x
    > end
    > end
    >
    > f = Foo.new
    > x = Foo.new
    > f.set(x)
    >
    > Now f references x.
    >
    > I suggest you get your hands on David's new book once it is out and in
    > the meantime consult those various introductory documents (can be
    > found via http://www.ruby-doc.org/).
    >
    > Cheers
    >
    > robert

    I am .. I just had a complete brain fart on this! I understand perfectly
    everything that's been mentioned now. Thank you so much for your help!

    --Aldric
     
    Aldric Giacomoni, Feb 19, 2009
    #17
  18. Ken Bloom wrote:
    > On Tue, 17 Feb 2009 20:25:28 -0500, Aldric Giacomoni wrote:
    >
    >
    >> I know I could just use rubytree, which looks quite nice, but I'd like
    >> to see what you guys would do about creating a tree and linking the
    >> nodes together.
    >> In C++ we'd just make pointers, so how would we do the equivalent in
    >> Ruby?
    >>

    >
    > The easiest equivalence is that essentially everything in Ruby is a
    > pointer and the . operator in Ruby is the equivalent of C++'s -> (This is
    > similar to how Java behaves as well.) The = operator changes where the
    > pointer points.
    >
    > There's no such thing in Ruby as a pointer to a pointer, nor is there any
    > such thing as a variable that's not a pointer at all.
    >
    > --Ken
    >
    >


    Understood now. Thank you :)
    --Aldrc
     
    Aldric Giacomoni, Feb 19, 2009
    #18
  19. 2009/2/18 Aldric Giacomoni <"aldric[removeme]"@trevoke.net>:
    > I know I could just use rubytree, which looks quite nice, but I'd like
    > to see what you guys would do about creating a tree and linking the
    > nodes together.
    > In C++ we'd just make pointers, so how would we do the equivalent in Ruby?
    >


    It depends .. if you are just making trees for the sake of trees (or
    measuring something on them) you can go with the simple Node object or
    an array structure that implements the nodes.

    On the other hand you may use a hash and forget about trees completely
    if your data is one flat value, and use multiple layers of hashes if
    you have something like vectors or strings where you can split the
    value into multiple parts naturally.

    ie {1=>{1=>{0=>[1, 1, 0]}, 2=>{3=>[1, 2, 3]}}, 2=>{3=>{4=>[2, 3, 4]}}}

    Thanks

    Michal
     
    Michal Suchanek, Feb 19, 2009
    #19
    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. gavnosis
    Replies:
    0
    Views:
    524
    gavnosis
    Aug 2, 2003
  2. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,133
  3. sharan
    Replies:
    4
    Views:
    693
    CBFalconer
    Oct 30, 2007
  4. raki
    Replies:
    1
    Views:
    1,150
    Alexey Smirnov
    Jun 24, 2009
  5. Jack
    Replies:
    1
    Views:
    132
    amber
    Apr 26, 2005
Loading...

Share This Page