Why Java Collections API does not have Tree implementation [closed]

Question

Just out of curiosity, I recently had to use a tree for one of my programs, i had to build a binary tree myself, but why does the Collections API does not have a default implementation of tree(or even a binary tree)?

I think there should be some strong reason why they decided not to include it in collections API.

Answer 1

I think there should be some strong reason why they decided not to include it in collections API.

I think that the reason is that nobody has come up with a good API for trees that is both

• general purpose enough to cover a wide range of use-cases, and
• useful enough to compensate for the performance overheads of being general.

(And where do you stop? Tree? Binary tree? N-ary tree? DAG? Graph?)

It is worth noting that neither Apache Commons Collections or Google Collections (aka Guava) have a tree API. However, there is an active Guava issue on this topic - http://code.google.com/p/guava-libraries/issues/detail?id=174 - so clearly at least some people agree with your point of view.

UPDATE

As of version 15.0, Guava now has tree support in the form of the TreeTraverser and BinaryTreeTraverser classes. But this may not be what you expect. In truth, these classes don't actually implement the tree data structure. Instead, you have to do this in a generic type parameter. Further to that, the Traverser classes even avoid making assumptions about the APIs of the node type. They do this by being abstract classes, and requiring the concrete traverser subtype to implement the operations that interrogate the tree; e.g. to get a node's children.

---

FWIW, TreeMap and TreeSet are not "tree APIs". They are tree-based implementations of the Map and Set APIs. The tree-ness is totally concealed by the public APIs, making these two classes completely unsuitable for use as general purpose trees.

Answer 2

IMHO, theoretically, Tree is not a type of collection, it's just a type of implementation. I mean there are abstract collections such as Set (unordered set of entries), List (ordered set of entries), Map (two sets of entries with relations between them), and there are their implementations: array, list (e.g. ArrayList and LinkedList), HashSet etc., all of them have their own advantages and disadvantages. Thus, Tree is just one of implementations (for lists, e.g.) which may give you (roughly) faster search than array but no access by index.

BTW, there is TreeMap ("Red-Black tree based NavigableMap implementation") and TreeSet ("A NavigableSet implementation based on a TreeMap.") classes in Java.