Making Good Software

A blog by Alberto G (Alberto Gutierrez)

Written by Alberto Gutierrez

July 25th, 2010 at 12:11 pm

Java and tree data structures.

with 18 comments

There isn’t any standard java implementation.

In almost every single project I have been involved, at some stage, I have found necessary to use a tree data structure, but I have found myself rewriting the same code to represent it because Java doesn’t provide with standard interfaces and implementations for Trees.

There are some open source tree data structures, but they are not flexible enough.

It is also surprising that there isn’t any major open source project, at least that I’m aware of, that tries to fill this gap. I have found on the Internet a few attempts to implement trees, but even thought they are correct, I don’t think they are as flexible as they should be.

The usual solution, the composite pattern on the objects itself, is far from ideal.

The most common implementation of trees, is using the composite pattern on the objects itself, meaning that no abstractions are created for classes as Tree, or Node. This approach has two main flaws:

  • Low cohesion: Now each object which is member of the tree needs to also have methods for navigation, insertion or other operations which are completely out of the scope of their own nature.
  • High coupling: Each node knows about their parents or about their children, changing one of them usually requires to changes the others as well.

How it should be (IMHO)

In my opinion, these are at least the main characteristics that a flexible Tree library should have.

  1. Ability to branch and sub-branch. Instead hanging nodes directly from other nodes, have the ability to add branches and sub-branches to nodes and hang the child nodes from them.
  2. XPath enabled. So you can call something like Node<Something> node = tree.get (“path/to/node”);
  3. Navigation specified through strategy. Navigator nav = tree.getNavigator (Strategy);
  4. Ability to filter.Navigator nav = tree.getNavigator (Strategy, Filter);
  5. Ability to create sub-trees from nodes. Tree subTree = new Tree (tree.get (“path/to/node”));
  6. Multi-threaded.

Your opinion and collaboration.

The main reason to write this article, is that I’m actually about to start writing this library myself, and I would like to share it with everyone, but before, I would like to hear from you guys. What’s your opinion: Do you think this sort of library would be useful? Would you use it? Do you think there are classes already that I might not know that have this functionality?

I am really looking forward for your comments!

Update

To find more information about the above mentioned Java tree library, including the SVN locations to download the source code check here.

18 Responses to 'Java and tree data structures.'

Subscribe to comments with RSS or TrackBack to 'Java and tree data structures.'.

  1. Sounds great! I’d love to see it/use it.

    tb

    26 Jul 10 at 4:32 am

  2. The need for such library is certain. An extension of google collections would be great, for example you could re-use the class com.google.common.collect.Constraint.

    Simon

    27 Jul 10 at 3:51 am

  3. Hi Simon!

    Thanks for your advice! I will certainly consider it.

    Thanks!

    Alberto Gutierrez

    27 Jul 10 at 5:11 am

  4. Hi Alberto!!, yeah, this is a good idea!!, maybe graph db, like neo4j, can help you. With this framework you can navigate it and you can save them.

    I don’t know if you are searching something like this, I like so much your ideas at ‘How it should be (IMHO)’

    Pablo Palazon

    27 Jul 10 at 7:03 am

  5. Hi Pablo!

    I didn’t know about neo4j, but I’m going to check it out.

    Thanks

    Alberto Gutierrez

    27 Jul 10 at 7:09 am

  6. I’m actually starting a project with Neo4J. I did a lot of research on this and it fits the bill for what I’m building perfectly.

    Jason

    27 Jul 10 at 4:33 pm

  7. Why limit yourself to trees? For full blown graphs, there is this great project called (http://www.jgrapht.org/). They have graphviz dot export, and all the basic graph algorithms you’d expect (http://www.jgrapht.org/javadoc/org/jgrapht/alg/package-frame.html), such as BellmanFordShortestPath, EdmondsKarpMaximumFlow, HamiltonianCycle and so on.

    Daniel Ribeiro

    27 Jul 10 at 9:42 pm

  8. @Daniel

    Yeah! I think you are right, it will be better if it supports graphs as well.

    Thanks for your comment!

    Alberto Gutierrez

    29 Jul 10 at 3:36 am

  9. You’re not alone in this!
    I’ve hit this issue a couple of times during my career, and the solution, as in your case, was to create my own tree implementation.
    Both times I needed because of a custom TreeTable widget (for Swing and now for GWT).
    In my opinion, javax.swing.tree.TreeModel is a nice definition of a tree. What I don’t like is the implementation (javax.swing.tree.DefaultTreeModel), which is tied to the TreeNode, and therefore to the Composite way of doing trees.
    If you’re interested, I could send you some code of my last implementation, which regarding to your points:
    1) YES – It’s easy to branch/re-branch, add/remove nodes, etc.
    2) NOPE
    3) YES – I have a couple of “external” iterators that knows how to traverse a tree.
    4) NOPE – But it would be easy to implement. One way is to wrap the tree with the data with an implementation that implements the read-only interface (e.g. ITree) and provides the filtering, or sorting, etc. So, the user of the “ITree” doesn’t need to know if the tree is filtered or sorted or both, in order to navigate it.
    5) YES
    6) NOPE – Because it’s for GWT I don’t need to worry about Threads 😛

    Cheers

    Luismahou

    27 Jul 10 at 10:54 pm

  10. @Luismahou

    Wow! Thanks, that’ll be great, for the comments I have so far, I see that there are very good tree implementations, I may just be looking into adapting them a bit to include the other functionality.

    Thanks!

    Alberto Gutierrez

    29 Jul 10 at 3:35 am

  11. Hi,

    if you consider neo4j (graph databases), where does fit JCR in this picture (say Jackrabbit) as it can be used for managing any content and being a standard API (http://dev.day.com/content/ddc/blog/2009/01/jcrrdbmsreport.html or http://java.dzone.com/articles/java-content-repository-best)?
    Regards,
    jgrd

    jgrd

    28 Jul 10 at 12:35 am

  12. […] This post was mentioned on Twitter by Richard Laksana, Chandan. Chandan said: Making Good Software:java-and-tree-data-structures: http://www.makinggoodsoftware.com/2010/07/25/java-and-tree-data-structures/ […]

  13. vad

    28 Jul 10 at 5:40 am

  14. @vad

    That’s actually an excellent tree implementation, and the code is very clean, I may take as a starting point and add a few functionalities

    Thanks

    Alberto Gutierrez

    29 Jul 10 at 3:36 am

  15. Hi I would like to help you with the implementation (if you need it).

    Julien

    2 Aug 10 at 7:41 pm

  16. Hi Julien!

    Thanks for the offering, I have actually not started, I am really busy lately as I’m moving to London, I hope to be a bit more relaxed in a couple of weeks when I hope I will start implementing this tree thing, I would let you know.

    Thanks!

    Alberto Gutierrez

    4 Aug 10 at 6:32 am

  17. Hi Alberto,
    did you write your own tree implementation? or did you find some good one?
    I have to implement a tree for the navigation in a web application. It will be helpful if you give me some feedback.

    Thanks!

    Eli

    9 Nov 10 at 5:23 am

  18. Once done,please send the link of the code to my email id.

    Deepak Lalchandani

    16 Nov 10 at 3:28 am

Leave a Reply