• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Who uses Trees?

 
Ranch Hand
Posts: 238
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
In trying to keep up with the current trend in programming, I keep running into academics who insist of parsing, pruning and sorting binary trees (and their cousins, binary search trees) when teaching a new language (or paradigm). After almost 20+ years of coding experience in other languages, I just want to know how many applications (other than possibly some high order Database work) actually use tree structures?

This often comes in many of the exercises in learning these new languages, and I am curious as to the fascination for this structure when most(?) applications usually use arrays, lists or other basic structures for their use.

Thanks!
 
Ranch Hand
Posts: 1272
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I had the same reaction at first.

Then I realized that many of my old programs would have been better with trees, just as I should have used quicksort instead of bubblesort.

Inserting a new element in the middle of a searchable ordered list is much faster with a tree structure. In algorithms class, you will learn to make that last statement with mathematical accuracy. This stuff is hard but useful. Hang in there!
 
Ranch Hand
Posts: 5093
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I use a lot of trees. In summer they provide shade, in autumn fruit, and in winter wood to make a fire.
And all through the year they can be turned into wood chips to make paper.
 
Ranch Hand
Posts: 1033
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Sam Smoot:
I just want to know how many applications (other than possibly some high order Database work) actually use tree structures?



The most obvious tree application on most desktop computers is the file system structure of files and folders within folders, and the manager or explorer that displays this. Another application of a tree structure is class inheritance in OOP languages.
 
Mike Gershman
Ranch Hand
Posts: 1272
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Peter:

All true, but I am guessing that Sam is asking about the use of trees in application code, not in system software.

I think many programmers would be amazed at how much faster their programs would run with better choices of searching and sorting algorithms. Even with Java collections or the C++ STL, you need to know when each technique is best.
 
Saloon Keeper
Posts: 27763
196
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Most commonly I use lists and hashmaps myself. I've occasionally indulged in other options if the situation warranted.

It depends on the nature of the job. A lot of graphics rendering is effectively managed by use of trees and other Graph Theory constructs.
 
peter wooster
Ranch Hand
Posts: 1033
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Mike Gershman:
Peter:

All true, but I am guessing that Sam is asking about the use of trees in application code, not in system software.

I think many programmers would be amazed at how much faster their programs would run with better choices of searching and sorting algorithms. Even with Java collections or the C++ STL, you need to know when each technique is best.



I agree that the use of proper data structures is one of the biggest differences between a slow program and a fast one.

Here are real application uses of trees, that can't easily be implemented without them:
- a project management program has a hierarchy of tasks
- a org chart program has a hierarchy of managers and their direct reports
 
Author
Posts: 6055
8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Sam Smoot:
In trying to keep up with the current trend in programming, I keep running into academics who insist of parsing, pruning and sorting binary trees (and their cousins, binary search trees) when teaching a new language (or paradigm).



I think it's clear that trees are used, although not ncssarily by everyone on a regular basis. Sam, what would you use when teaching a new language instead? (BTW, I'm assuming your claiming that the language class using trees is in addition to an algorithms class.)

--Mark
 
Sam Smoot
Ranch Hand
Posts: 238
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yep, just about any "new" language class often has an exercise reading, displaying, pruning and comparing trees. As to what/how I would teach a class now, I have no idea. I am just now getting comfortable with the idea of OO. (Until 1999, I had 12 years of dedicated Mainframe Assembler experience). I'm now trying to complete an undergrad degree in Software Engineering and I keep running into these data structures with no idea as to how to apply them in a context I can fully understand . I do understand the theories tied to them (from a Discrete Structures class), but, outside of that, a tree belongs, well, outside .

Currently I am in a class where we are learning the differences between the programming paradigms using Scheme, Prolog, Ada, C++ and Java. Personally, Prolog kicked my butt, while Scheme is running a close second (did I mention we only get about 3 weeks per language with no dedicated resources for learning them? ). Fortunately, the C++ and Java (actually, Java) are part of the core for the Computer Science department so that isn't as big an issue any more...

Oh yeah, the algorithms class is next fall... :roll:
[ March 14, 2005: Message edited by: Sam Smoot ]
 
Mike Gershman
Ranch Hand
Posts: 1272
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sam:

Be absolutely sure you have the earlier courses down pat before you take algorithms. There are lots of online resources, including practice exercises. I used to use some MIT class pages to practice recurrences and Master Theorem (be afraid, be very afraid).

In the end, you'll not only get it but use it at work. You spent years learning how, now you're learning why. The people who designed the languages and software we work with based their work on the same stuff you are studying, so things will make more sense when you understand the theory.

If you are having trouble with Scheme, try "The Little Schemer". Maybe someone can suggest a resource for Prolog.

You will know you are finally getting it when you realize that code you wrote years ago could have been done a lot better.
 
Sam Smoot
Ranch Hand
Posts: 238
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That's a good Idea, however, I only have about 5 more days to "Scheme" then it's off to 3 weeks of Ada...

And thanks for the "warning"... I'm looking forward to another semester of "AAAAUUUUGGGHHHHHH!!!"

As to the code I wrote years ago, well, Mainframe assembler doesn't play well with a lot of these Ideas, but hey, who knows...
 
Tim Holloway
Saloon Keeper
Posts: 27763
196
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Mark Herschberg:


I think it's clear that trees are used, although not ncssarily by everyone on a regular basis. Sam, what would you use when teaching a new language instead? (BTW, I'm assuming your claiming that the language class using trees is in addition to an algorithms class.)

--Mark



I know what I'd use. Collections. One way of considering a tree is as a collection of collections. Binary trees, of course have collections of size 2.

Seriously, having spent years on working with a wide variety of projects, the patterns I ran into most commonly where the manipulation of data was the issue (as opposed to computation on the data) were almost invariably related to the creation, manipulation and/or enumeration of collections.

If there were any further incentive needed, consider the popularity of XML. Every well-formed XML document is a tree, by definition.
 
Mark Herschberg
Author
Posts: 6055
8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Tim Holloway:
[QB]
I know what I'd use. Collections.... Seriously, having spent years on working with a wide variety of projects, the patterns I ran into most commonly where the manipulation of data was the issueQB]



I think you missed the crux of the question. Perhaps collections are more common than trees (I haven't thought about to argue one way or another), if they are, they should be included in an algorithms class. In a language class the purpose of using trees is to help teach the language, not algorithms,* so the question becomes which is a better teaching tool.

*I'm assuming a language intro class as part of a larger curriculum. Obviously stand-alone classes which might combine language and algorithms may have different constraints, but I believe we're talking about professors who primarily teach matriculated students.

--Mark
 
reply
    Bookmark Topic Watch Topic
  • New Topic