What does tree mean in java TreeMap?

Question

I am new to java, especially java collections. Java data-structure TreeMap does not have any methods (like getChildren, getParent) to suggest that it holds a hierarchical structure. What is the significance of word tree in the class-name?

Have you read the official JavaDoc on this Java class: http://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html ? — MWiesner, Dec 19 '15 at 14:06
Out of votes. http://stackoverflow.com/questions/33251375/java-why-treemap-is-called-tree-map — Sotirios Delimanolis, Dec 19 '15 at 14:14

score 1 · Answer 1 · edited May 23 '17 at 12:15

1

In two words, TreeMap means that it is a Map implementation where the data is stored in a tree-like structure. This leads to the fact that elements are sorted by their keys (TreeMap implements SortedMap).

Here is good visualisation of red-black tree.

Other types of maps in Java are HashMap and LinkedHashmap. You can find differences here.

edited May 23 '17 at 12:15

Community

1
1

answered Dec 19 '15 at 14:14

Gaket

6,533
2
37
67

The link you have provided for the red-black tree visualization: http://www.cs.usfca.edu/~galles/visualization/RedBlack.html does not work – Nuwan Jayawardene Dec 18 '17 at 06:27
1

I've checked it just now, It works on my Safari and Chrome. You should enter some number into text field in left top corner, near "Insert" button and press "Insert" to start. – Gaket Dec 18 '17 at 07:30
1

Yes it working! Thanks for the update :) – Nuwan Jayawardene Dec 18 '17 at 08:35

score 0 · Answer 2 · answered Dec 19 '15 at 14:09

The "tree" part gives away an implementation detail of the class. According to the documentation, TreeMap is

A Red-Black tree based NavigableMap implementation.

The name OrderedMap or SortedMap would probably be better, but "tree" is good enough to convey the way the class works to its users.

score 0 · Answer 3 · answered Dec 19 '15 at 14:13

A TreeMap is essentially a Red-black tree which is a balanced search tree. The main purpose of this tree is ensure O(lg(n)) lookup and not modelling a hierarchies.

If you look at the code of TreeMap, you will find that it has TreeMap.Entry which is defined as follows.

 static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
  ..
 }

But OOP tells us that implementation details shouldn't be exposed

score 0 · Answer 4 · answered Dec 19 '15 at 14:13

The data structure is principally a map, not a tree. But the map is implemented using a tree. A TreeMap provides an efficient means of storing key/value pairs in sorted order, and allows rapid retrieval. As it is a map to the user, you don't need to get parent of any node in the tree, or its child, hence no getParent or getChildren function is available.

What does tree mean in java TreeMap?

4 Answers4