Understanding TreeMaps

Question

this is a noobie question regarding tree maps. I have read through the Java API and other documentation but am still unclear about just how this works.

From my understanding, a Tree in java (or any language) is sort of like a family tree; where you have say:

Layer 1                               OldestGuy    
Layer 2       OldGuy1       Oldguy2         OldGuy3        OldGuy4           OldGuy5
Layer 3   Guy1 Guy2 Guy3 Guy4 Guy5  Guy6........ etc

Where Layer 1 has 1 value (i.e. a central node) and from there there can be arbitrary amounts of values (or Guys) in each subsequent layer, and some of the "branches" can be longer than others (for example it could go OldestGuy -> OldGuy1 -> Guy1 & Guy2...Guyn whilst at the same time another branch is just OldestGuy -> OldGuy4)

With this ind mind I am trying to add values to a TreeMap in specific locations of specific branches whilst making specific connections but all I seem to be getting is the same results as a HashMap.

(it seems what I want to do requires something more than the TreeMap ....as the Key (or Layer(?) would be the same for several different values)

Any suggestions / explanations would be fantastic because I feel as if I am seriously barking up the wrong tree with this one.

I have seen examples of this being done using googles .jar, (such as a family tree) but I am just trying to understand this as there seems to be lots of conflict between TreeMap and Trees and how you can store data in them.

Satisfaction

+1 for barking up the wrong tree. – Nimble

Answer 1

TreeMap is just an implementation of Map that happens to use a red-black tree behind the scenes. The details of the tree aren't exposed to you, so you can't store elements in arbitrary locations.

To put it another way, a TreeMap is not a general-purpose tree data structure. If that's what you actually want, perhaps take a look at this Stack Overflow question: Java tree data-structure?.

Amicable

Thanks for the explanations guys, I guess I was being hung up on the Tree portion and was hoping there was a way to go to specific nodes. Guess its time to learn about JTree = D – Satisfaction

Answer 2

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, Serializable

• Tree Map does not use hashing for storing keys. It's use Red-Black tree(self-balancing binary search tree.).
• The TreeMap is sorted according to the natural ordering of its keys. Tree Map will always have all elements sorted.
• Working of Tree Map is based on tree data structure.
• Tree Map is not Synchronized and hence not thread safe.
• Tree Map in java doesn't allow null key,but allow multiple null values.

Working of Tree Map is based on tree data structure.

• Each node have 3 reference : PARENT,LEFT and RIGHT.
• LEFT elements always less than parent element.
• RIGHT elements always grater or equals of parent element.

Rikki

Answer 3

A Java TreeMap uses a tree as an internal data structure to get O(log n) lookups and inserts, but doesn't expose its tree structure in its interface. So there's no way to, for instance, get a tree node and all its descendants, or represent a family tree using it.

Underbelly

Answer 4

TreeMap is a Map (implemented via a tree), not a tree (implemented via a Map or otherwise).

Kyle

Answer 5

I think you are confusing two different things. A TreeMap is implemented as a Red-Black Tree.
Per the Java doc:

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

So, in essence if you want to have a predictable ordering of your keys you should either leave the TreeMap to order your keys by using natural ordering or implement the Comparator interface yourself. Again, from the Javadoc:

Note that the ordering maintained by a tree map, like any sorted map, and whether or not an explicit comparator is provided, must be consistent with equals if this sorted map is to correctly implement the Map interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Map interface is defined in terms of the equals operation, but a sorted map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.

Now, it isn't clear if you want to place your keys in the way that I mentioned (i.e natural ordering) or in another way (i.e. insertion order or something else?).
For example, if you prefer insertion order the LinkedHashMap might prove better for your case.
If something else is the case please specify it :].

Uproar