What java datastructure/library do you use for a Tree

views:

144

answers:

+3 Q:

What java datastructure/library do you use for a Tree

I have a Region Hierarchy(think State, District, Taluk, etc) that I need to represent using a Tree. I saw a few implementations of a Tree in the public domain BUT not sure how good they are and how well they are maintained. Apache Collections doesn't have one of those NOR do the google collections. I'm wondering if any of you can point me to an implementation of a Tree in Java(with generics).

Thank you,

Update I am looking for a Tree Datastructure, preferably implemented using Generics : well tested.

+1 A:

Implementing a tree using generics is pretty simple, why not give it a try yourself? If you're not comfortable with generics, you can try declaring a tree that contains elements that implement an interface, then just have all your various region elements implement that interface.

TMN 2010-07-12 16:40:02

I have implemented trees several times in C/C++ long time ago. If there was something I could reuse, I'd rather use something unit tested and time tested!

anjanb 2010-07-12 17:53:24

A basic tree is easy to implement. But serious trees require some rebalancing (e.g. Red-Black trees.) Those take time to get right and efficient. For example, from what I remember, there are 7 different rotation cases for RB-trees.

Dilum Ranatunga 2010-07-12 22:12:54

If you rebalance a RB tree then you are interested in the ordering property of the tree, not the structural qualities (parent, children). If that's the case, then Java absolutely has TreeSet which does exactly that, check the libraries. If you want a "Tree Structure" to track parent/child relationships than the implementation is trivial and your objection makes no sense.

Bill K 2010-07-12 22:29:59

@Dilum: Agreed, balanced trees aren't trivial to implement. However, from the problem statement, it didn't seem that a binary tree would be appropriate, since the tree needs multiple children per node. I was thinking a threaded tree would probably be applicable, since it appears it would be handy to have a tree that can be traversed in either direction.

TMN 2010-07-13 13:46:50

+1 A:

Do you mean a Tree Widget or a tree like data structure? If you are talking about a Tree widget, then Swing has an implementation.

JTree

Am 2010-07-12 16:41:11

thanks. I meant a Tree Datastructure.

anjanb 2010-07-12 17:52:23

+1 A:

What you're describing is much more like a Document Object Model (DOM). Usually when people refer to a "Tree" data structure, they're talking about a balanced binary tree (like a red-black tree, which certainly does exist in the Java collections library). But those kinds of trees are just for fast in-order insertions and lookups.

Anyhow, most of the time, when people use a DOM, they're reading or writing XML, but there's no reason you couldn't use a DOM for your own arbitrary hierarchical data. Even if you never persist it to XML.

benjismith 2010-07-12 16:46:28

DOM. how expensive is DOM when you're NOT using it for XML ?

anjanb 2010-07-14 06:38:46

I don't really know, but I can speculate about a few things... The reason why DOM is considered an expensive XML-parsing technique is that you have to parse the whole XML file and keep it in memory, rather than scanning through the XML and firing SAX events. But in your case, you need the whole document in memory anyhow, so I wouldn't think a DOM implementation would be much more expensive than whatever custom data structure you might roll yourself. (And of course, you won't pay the I/O cost.) Then again, you'll have to live with the specific semantics of XML in your own tree model.

benjismith 2010-07-15 00:37:27

+1 A:

Would something like this http://www.java-tips.org/java-se-tips/java.lang/red-black-tree-implementation-in-java.html work?

Also, how about starting with the java.util.TreeMap source from the OpenJDK? http://download.java.net/openjdk/jdk7/

Dilum Ranatunga 2010-07-12 22:20:00

Those implementations are for binary trees. Can each state only have two districts, and each district only two taluks? If so, then those might work. If you need to accomodate more than two instances of each level in the hierarchy, though (and I'm guessing you do), then you'll want to roll your own. I did this a couple weeks ago for some XML parsing I was doing, and it only took me a couple of hours to get it designed, tested, written and documented. I can't share the code (it's in C# anyway), but I could share the design if you don't want to work up something on your own.

TMN 2010-07-13 13:53:44

+1 A:

Check out DefaultMutableTreeNode. It's not generic, but otherwise seems to fit the bill. Even though it's in the javax.swing package, it doesn't depend on any AWT or Swing classes. In fact, the source code actually has the comment // ISSUE: this class depends on nothing in AWT -- move to java.util?

Mark 2010-10-14 12:25:28

ansaurus

tags:

views:

answers:

What java datastructure/library do you use for a Tree

related questions