The java.util.TreeMap class implements the Map interface using a balanced binary search tree ordered by keys. In general, any Comparable objects may be placed into a TreeMap as the key. This guarantees that the keys will be in ascending order, as determined by the key object’s compareTo method.

Because of the balanced binary tree implementation, the TreeMap class provides an O(log n) run time for the operations put, get, and containsKey.

The following code fragment demonstrates implementation of a TreeMap:

TreeMap<Integer, String> studentMap = new TreeMap<Integer, String>();

for ( int recNum = 1; recNum <= NUM_STUDENTS; recNum++ )
{
  Student s = new Student();      // declare a new Student
  s.setName(...);                 // set the student’s
                                  // attributes
  s.setGradeLevel(...);           // ...
  s.setID(...);                   // ...

  studentMap.put( s.getID(), s ); // add student to the map
                                  // using ID as the key
}
// Display the student whose key is S964413
System.out.println( studentMap.get( "S964413" ) );

The Map interface does not specify a method for obtaining an iterator, and the TreeMap class does not have one. Instead, you can get the set of all keys by calling the keySet method, then iterate over that set to get all values. For example:

TreeMap<String, Definition> acronym = new TreeMap<String, Definition>();
String key;
Definition value; // acronym definition

acronym.put( "CS", new Definition( "Computer Science" ) );
acronym.put( "AP", new Definition( "Advanced Placement" ) );

Set<String> keys = acronym.keySet();
Iterator<String> iter = keys.iterator();
while ( iter.hasNext() )
{
  key = iter.next();
  value = acronym.get( key );

  // process value
  System.out.println( key + " stands for " + value.getDefinition() );
}

The output for this code fragment is

AP stands for Advanced Placement
CS stands for Computer Science

The values will be processed in the ascending order of keys.

TreeMap is more general than TreeSet. Both implement Binary Search Trees, but in TreeSet the values are compared to each other, while in TreeMap, no ordering is assumed for the values and the tree is arranged according to the order of the keys. In a way, a set is a special case of a map where a value serves as its own key.

import java.util.TreeMap;

TreeMap<Integer, String> map = new TreeMap<Integer, String>();
String name = "John";
map.put( new Integer(3), name );
map.put( new Integer(2), "Nancy" );
map.put( new Integer(1), "George" );

System.out.println( "Size of map: " + map.size() );
System.out.println( "Name associated with key = 1:" + map.get( 1 ) );

The output for this code fragment is

Size of map: 3
Name associated with key = 1: George