• Post Reply Bookmark Topic Watch Topic
  • New Topic

Trees  RSS feed

 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,

I am currently learning data structures (along with Java). When I learnt about arrays and linked lists, I am able to visualize how those are built - as they seem pretty straightforward and you also have implementations in Java so you can use "new" to create create new arrays or linked lists. But with trees, I am not able to imagine the structure and there are also no implementations in Java. I am not sure if my question is clear! I'd just like a way to understand trees just like I do arrays and linked lists.

Also, why is there no implementation in Java? Are trees considered not common enough to have an implementation as they have for Arrays, Linked lists, Hash tables and other data structures?
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Prasanna Raman wrote:I am currently learning data structures (along with Java). When I learnt about arrays and linked lists, I am able to visualize how those are built - as they seem pretty straightforward and you also have implementations in Java so you can use "new" to create create new arrays or linked lists. But with trees, I am not able to imagine the structure and there are also no implementations in Java. I am not sure if my question is clear! I'd just like a way to understand trees just like I do arrays and linked lists.

The only thing I can suggest is that you do some Googling. Several of the Wikipedia pages have very nice GIFs that show you how they work.
Be warned though: there are MANY types of trees.

Also, why is there no implementation in Java? Are trees considered not common enough to have an implementation as they have for Arrays, Linked lists, Hash tables and other data structures?

There are at least two, and they both start with the word "Tree": TreeSet and TreeMap.
However, if you're looking for anything that's going to give you an idea of how they work internally, forget it. The whole point of Object-Orientation is to hide that stuff from you.

Winston
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:
Prasanna Raman wrote:Also, why is there no implementation in Java? Are trees considered not common enough to have an implementation as they have for Arrays, Linked lists, Hash tables and other data structures?

There are at least two, and they both start with the word "Tree": TreeSet and TreeMap.


From the user's perspective though, those aren't trees. They're a Set and a Map, respectively. We don't get to use their tree features, just benefit from them indirectly.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jeff Verdegan wrote:From the user's perspective though, those aren't trees. They're a Set and a Map, respectively...

Hmmm, interesting point. Never really thought about it that way.

I've always thought of it as an algorithm for arranging ordered elements efficiently. I can certainly imagine a structure that looks like a tree, but can't for the life of me think what the API would be like that would allow me to use it as one.

Do you have any examples?

Winston
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:Do you have any examples?


The DOM for an XML doc springs to mind. DOM APIs have methods like getChildren() and so on that let you interact and navigate pretty directly in the tree structure.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jeff Verdegan wrote:The DOM for an XML doc springs to mind. DOM APIs have methods like getChildren() and so on that let you interact and navigate pretty directly in the tree structure.

Aaah, yes.

Cheers.

Winston
 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So, why would Java not have an implementation for tress as they do for Arrays, Linked lists etc.? Are trees not so commonly used as the others?
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Prasanna Raman wrote:So, why would Java not have an implementation for tress as they do for Arrays, Linked lists etc.? Are trees not so commonly used as the others?

It does. I've given you two - although, as Jeff points out, they're only used internally - and he gave you a third, which really IS a tree; albeit a highly specialized one.

My question to you is the same as I gave to Jeff: What would you use a tree for, and what would its API look like?
Don't forget that we're talking about a generalized tree here - Java isn't usually in the habit of creating highly specialized classes; especially in the Collections framework. They leave that to Apache.

Winston
 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:
My question to you is the same as I gave to Jeff: What would you use a tree for, and what would its API look like?

Winston


I actually don't know the answer to this question, Winston I am actually only starting to learn the various data structures, and I don't really have much of an idea about the applications that could use them. But I have seen Java's implementations of arrays and hash tables but not trees directly. That's why I asked the question.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Prasanna Raman wrote:I actually don't know the answer to this question, Winston I am actually only starting to learn the various data structures, and I don't really have much of an idea about the applications that could use them. But I have seen Java's implementations of arrays and hash tables but not trees directly. That's why I asked the question.

Well actually, only one of those is really a specific "structure" (array). "Hashed" collections are much more like "trees" in that they're provided as Sets or Maps; you don't actually get to see any of the inner workings (although it's probably worth knowing that they do rely on a good hashCode()).

Be assured: TreeSet and TreeMap are, in fact, trees, so you do have at least two provided for you directly. In fact, as I recall, they're red-black trees (something else to look up ).

Winston
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Prasanna Raman wrote:So, why would Java not have an implementation for tress as they do for Arrays, Linked lists etc.? Are trees not so commonly used as the others?


Probably because they're not as commonly used as a general container. I use List<X>, Set<X>, and Map<X, Y> all the time. I think once about 8-10 years ago I found myself wanting either a Tree<X> or perhaps it was BinaryTree<X>, but after a bit of research and messing about it turned out I was over-engineering the problem.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!