How do I define a tree structure in Perl 
Author Message
 How do I define a tree structure in Perl

Hi,

I would like a tree data structure with the ability to search the tree.

Thanks for any help

Brent



Mon, 28 Jun 2004 22:54:50 GMT  
 How do I define a tree structure in Perl

Quote:
> I would like a tree data structure with the ability to search the tree.

Please see "perldoc perlref"

jue



Mon, 28 Jun 2004 23:00:57 GMT  
 How do I define a tree structure in Perl

Quote:

> Hi,

> I would like a tree data structure with the ability to search the tree.

I doubt you really want that. Perl has something that is much easier in
usage and most often all you really need: hashes.

However, you can read about something similar in the FAQs:

    'perldoc -q linked'

will give you a little bit on linked lists which are sort of related to
trees. You should be able to modify the examples according to your
needs.

Tassilo
--
$_=q!subJust{another()};subanother{Perl()};subPerl{hacker()};subhacker{map

b/(reverse"bus").chr(32)/xge;tr~\n~~d;eval;



Mon, 28 Jun 2004 23:03:12 GMT  
 How do I define a tree structure in Perl


Quote:

> > I would like a tree data structure with the ability to search the tree.
> I doubt you really want that. Perl has something that is much easier in
> usage and most often all you really need: hashes.

But if you do want to make a tree for your nefarious ends, then do see
the manpages the other posters have pointed you to. Is it a binary tree
(I didn't do a CS degree so my terminology may be wrong) like:

$node = {
   content => 'Hello world',
   child_less => $child_node_a,
   child_more => $child_node_b,
   parent => $parent_node,

Quote:
};

or some leafier construct:
$node = {
   content => 'Hello world',
   children => [ $long, $list, $of, $nodes ],
   parent => $parent_node,

Quote:
};

or something else? Do you have example code, or maybe something in C
that you're trying to do?

P

--
pkent 77 at yahoo dot, er... what's the last bit, oh yes, com
Remove the tea to reply



Mon, 28 Jun 2004 23:41:36 GMT  
 How do I define a tree structure in Perl

Quote:




>> > I would like a tree data structure with the ability to search the tree.
>> I doubt you really want that. Perl has something that is much easier in
>> usage and most often all you really need: hashes.

> But if you do want to make a tree for your nefarious ends, then do see
> the manpages the other posters have pointed you to. Is it a binary tree
> (I didn't do a CS degree so my terminology may be wrong) like:

Well, basically it's a tree. A binary one would be a tree with at most
two children per node. ;-)

Quote:
> $node = {
>    content => 'Hello world',
>    child_less => $child_node_a,
>    child_more => $child_node_b,
>    parent => $parent_node,
> };

That's actually more or less what I had been initially referring to. One
naturally uses a hash for the structure. I am sure these things are
sometimes done without people realizing they created a tree or linked
list.

But I think that thinking in such terms is misleading when using Perl.
It may be the wrong way of thinking to me.

Tassilo
--
$_=q!subJust{another()};subanother{Perl()};subPerl{hacker()};subhacker{map

b/(reverse"bus").chr(32)/xge;tr~\n~~d;eval;



Mon, 28 Jun 2004 23:48:25 GMT  
 How do I define a tree structure in Perl
On Thu, 10 Jan 2002 16:54:50 -0500,

Quote:
> Hi,

> I would like a tree data structure with the ability to search the tree.

Others have already suggested that you might use a hash instead of a
tree. Your question suggests that searching is the main thing that
needs to be fast, and a hash will be the better solution there. They
generally provide results in O(1) while trees search in O(log n). If
your main concern is storing things and then fetching them again
quickly, a hash will beat most other approaches.

If you do indeed need a tree, for example because you need the data to
be ordered, you could have a look at one of the various Tree:: modules
on CPAN (http://search.cpan.org) before attempting to implement one
yourself. Note that there are many different tree structures, and
which one is best depends on what you need to do and the
characteristics of your data and insertion process.

If you implement one yourself, and if you have to store a large number
of nodes in this tree, I'd suggest that you don't use a hash reference
to implement a node, since the memory overhead will be large. You
could use an array instead, or a pseudo-hash if you still like it to
look like a hash in your program (see the fields pragma
documentation).

If you really just need an ordered set you could consider just using
an array with the appropriate insertion (binary search followed by an
insertion) and fetching methods (binary search). I'd probably create a
tied interface for that (see the perltie documentation).

Next time you have a question, consider that it doesn't hurt to
provide a bit more information, so that people answering you don't
have to second-guess what you're trying to do or achieve.

Martien
--
                                |
Martien Verbruggen              | Unix is the answer, but only if you
Trading Post Australia Pty Ltd  | phrase the question very carefully
                                |



Tue, 29 Jun 2004 00:14:46 GMT  
 How do I define a tree structure in Perl

Quote:

> I would like a tree data structure with the ability to search the tree.

If you're willing to buy a book, "Mastering Algorithms with Perl"
http://www.amazon.com/exec/obidos/ASIN/1565923987/
has almost an entire chapter devoted to binary tress and other such
complex data structures.  I'm in the middle of the book now.  I like
it. :)

===============================================
Dave Hoover
"Twice blessed is help unlooked for." --Tolkien
http://www.redsquirreldesign.com/dave/



Tue, 29 Jun 2004 04:55:53 GMT  
 How do I define a tree structure in Perl
Martien

Good point about asking a open ended question.  I was asking on behalf of
someone else and I only had 1 minute to formulate a question.  Next time I will
not post in such a hurry.

Not sure I can spin this, other than say that certainly a lot of ideas thrown
out here on an open ended question- which was actually what I had hoped for.  

The data structure that is needed results from parsing plain c code.  Each node
represents a level of execution, where a level is separated by "{ }" characters
or a singular branch statement such as an "if" statement. Function calls are not
considered branch nodes for this execercise.  I was just thinking that a binary
tree would not work, because an if-else if-else if-else if-else could represent
more than two branches on a single node.

Thanks to everyone for their thoughts and info.

Brent

Quote:

> On Thu, 10 Jan 2002 16:54:50 -0500,

> Next time you have a question, consider that it doesn't hurt to
> provide a bit more information, so that people answering you don't
> have to second-guess what you're trying to do or achieve.

> Martien
> --
>                                 |
> Martien Verbruggen              | Unix is the answer, but only if you
> Trading Post Australia Pty Ltd  | phrase the question very carefully
>                                 |



Tue, 29 Jun 2004 15:32:30 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. Perl Data Structures: trees etc...

2. How to define a structure in PERL?

3. How to manage tree structures in perl

4. Tree of user defined objects

5. Tree of user defined objects

6. problem trying to define my data structure

7. Variable length array of arrays into tree structure - help

8. Simple tree data structure

9. Maybe too academic: How to build a (binary) tree (structure)

10. tree structure

11. how to store tree structure

12. Help with tree-like data structure (I think)

 

 
Powered by phpBB® Forum Software