Reputation:

Java: why TreeMap is called "Tree" map?

I can't understand why TreeMap is called TreeMap but not SortedMap. As I understand TreeMap is a map that auto sorts its elements. Tree in computer science is like a graph. So why?

Upvotes: 5

Answers (4)

Yogesh Sharma

Reputation: 280

Yes, Java Internally uses Red-black tree as a data structure in the implementation. Red black tree is a self balancing binary search tree and used here for keeping elements sorted based on the comparator implementation you provide or the natural order of keys. So if you look at the implementation of TreeMap.getEntryUsingComparator(Object) method (which is internally called from TreeMap.get(Object) method) below -

final Entry<K,V> getEntryUsingComparator(Object key) {
    @SuppressWarnings("unchecked")
        K k = (K) key;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = cpr.compare(k, p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

This is searching by looping and comparing the given given key to the root of the tree and deciding which branch we should go, either left or the right one. This was just to show that it is tree based that is why it is named like TreeMap.

Upvotes: 1

Rahul Tripathi

Reputation: 172458

As said by F. Ju, TreeMap is implemented by Red–black tree. You can also see the Javadocs:

Red-Black tree based implementation of the SortedMap interface. This class guarantees that the map will be in ascending key order, sorted according to the natural order for the key's class (see Comparable), or by the comparator provided at creation time, depending on which constructor is used.

Note that the ordering maintained by a sorted map (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 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.

Upvotes: 2