o7planning

Java TreeMap Tutorial with Examples

  1. TreeMap
  2. How does TreeMap store data?
  3. Examples
  4. TreeMap with null key

1. TreeMap

In this article we will explore TreeMap class, which is an implementation of Map interaface and resides in the Java Collection Framework.
public class TreeMap<K,V> extends AbstractMap<K,V>
                    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
Basically, in this article we will learn the characteristics of TreeMap and how it stores mappings. The basic concepts of Map will not be mentioned again, if you do not know the concept of Map, you should learn it before continuing with this article.
Map<K,V>
SortedMap<K,V>
NavigableMap<K,V>
TreeMap<K,V>
Duplicate keys are not allowed.
Can allow null key and null values.
Only null key are allowed if a suitable Comparator is provided.
The order of the keys is not guaranteed.
The keys are sorted in ascending order based on their natural order or according to a provided Comparator.
Inherits the features of SortedMap interface. All TreeMap keys must be Comparable type or you must provide a Comparator for TreeMap which compares keys. Otherwise, ClassCastException will be thrown. Comparator is provided at the time TreeMap object is created through one of its constructors.
TreeMap​ constructors
TreeMap()

TreeMap​(Map<? extends K,​? extends V> m)    

TreeMap​(Comparator<? super K> comparator)

// Using the same ordering as the specified sortedMap.
TreeMap​(SortedMap<K,​? extends V> m)

2. How does TreeMap store data?

TreeMap uses comparator.compare(key1,key2) to compare two keys if Comparator is provided. Otherwise it uses key1.compareTo(key2) to compare two keys. TreeMap is designed to ensure that searching, updating, or deleting a map takes as little time as possible by reducing the number of times keys have to be compared. In this section we will learn about how TreeMap stores its data.
Entry<K,V> is a class used to store a mapping, which consists of 5 properties: key, value, parent, left, right. TreeMap manages a reference to a root Entry - root. TreeMap searches will start at the root Entry and propagate to a leaf of the tree.
Entry<K,V>
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
For easy understanding, let's see what happens when we add mappings to a TreeMap<Integer,String>.
TreeMap<Integer, String> map = new TreeMap<>();

// keys = 5, 3, 9, 7, 1, 11.
map.put(5, "Five");
map.put(3,  "Three");
map.put(9,  "Nine");
map.put(7, "Seven");
map.put(1, "One");
map.put(11, "Eleven");
The image above shows the tree structure of TreeMap. The first mapping added to the TreeMap will be the root of the tree, the mapping with the smaller key will be placed on the left, and the mapping with the larger key will be placed on the right.
get(key)?
map.get(7); // key =  7
The operation of finding a mapping always starts at the root Entry. The key to search will be compared with the current Entry key, if greater it will be compared with the next Entry key on the right. Otherwise if it is smaller, it will be compared with the next Entry key on the left, until found or reached the leaves of the tree.
remove(key)?
Next, let's see what TreeMap does to remove a mapping.
map.remove(5); // Remove the mapping has key = 5.
To remove a mapping, the TreeMap identifies the location of the Entry to be removed. Then it searches for the Entry with the smallest key and greater than the key to be removed to replace it in the position of the Entry to be removed.
put(key,value)?
map.put(2, "Two");

3. Examples

As we all know, Integer class implements Comparable interface, so Integer objects can be compared with each other. TreeMap with Integer keys do not need to provide a Comparator.
TreeMapEx1.java
package org.o7planning.treemap.ex;

import java.util.Set;
import java.util.TreeMap;

public class TreeMapEx1 {

    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        //  
        map.put(5, "Five");
        map.put(3, "Three");
        map.put(9, "Nine");
        map.put(7, "Seven");
        map.put(1, "One");
        map.put(11, "Eleven");
        
        Set<Integer> keys = map.keySet();
        
        System.out.println(keys);
        
        for(Integer key: keys)  {
            System.out.println(key + " --> " + map.get(key));
        }
    }
}
Output:
[1, 3, 5, 7, 9, 11]
1 --> One
3 --> Three
5 --> Five
7 --> Seven
9 --> Nine
11 --> Eleven
Example: Use the custom Comparator to reverse the keys order.
TreeMap_reverseOrder_ex1.java
package org.o7planning.treemap.ex;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeMap;

public class TreeMap_reverseOrder_ex1 {

    public static void main(String[] args) {
        Comparator<Integer> reverseOrderComparator = Comparator.reverseOrder();
        
        TreeMap<Integer, String> map = new TreeMap<>(reverseOrderComparator);
        //  
        map.put(5, "Five");
        map.put(3, "Three");
        map.put(9, "Nine");
        map.put(7, "Seven");
        map.put(1, "One");
        map.put(11, "Eleven");
        
        Set<Integer> keys = map.keySet();
        
        System.out.println(keys);
        
        for(Integer key: keys)  {
            System.out.println(key + " --> " + map.get(key));
        }
    }
}
Output:
[11, 9, 7, 5, 3, 1]
11 --> Eleven
9 --> Nine
7 --> Seven
5 --> Five
3 --> Three
1 --> One
See more examples of using the custom Comparator and how to navigate, search for key or mapping:

4. TreeMap with null key

TreeMap only allows null keys if it is provided with a Comparator that supports comparing null key with other keys.
TreeMap_nullKey_ex1.java
package org.o7planning.treemap.ex;

import java.util.Comparator;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

public class TreeMap_nullKey_ex1 {

    public static void main(String[] args) {
        // Comparator.nullsFirst
        // Comparator.nullsLast
        Comparator<String> comparator = Comparator.nullsFirst(Comparator.naturalOrder());

         // Create a SortedSet object.
        SortedMap<String, Integer> map = new TreeMap<String, Integer>(comparator);
 
        map.put(null, 0);
        map.put("B", 100);
        map.put("A", 200);
        map.put("F", 400);
        map.put("D", 500);
        map.put("E", 100);

        System.out.println("--- keySet ---");
        Set<String> keys = map.keySet();

        for (String key : keys) {
            System.out.println(key + " --> " + map.get(key));
        }
        
        System.out.println("--- entrySet ---");
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        
        for (Map.Entry<String,Integer> entry: entrySet) {
            System.out.println(entry.getKey() + " --> " + entry.getValue());
        }
    }
}
Output:
--- keySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400
--- entrySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400
Example: Write a custom Comparator that supports comparing null key with other keys:
TreeMap_nullKey_ex2.java
package org.o7planning.treemap.ex;

import java.util.Comparator;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

public class TreeMap_nullKey_ex2 {

    public static void main(String[] args) {  
        Comparator<String> comparator = new StringNullComparator();

         // Create a SortedSet object.
        SortedMap<String, Integer> map = new TreeMap<String, Integer>(comparator);
 
        map.put(null, 0);
        map.put("B", 100);
        map.put("A", 200);
        map.put("F", 400);
        map.put("D", 500);
        map.put("E", 100);

        System.out.println("--- keySet ---");
        Set<String> keys = map.keySet();

        for (String key : keys) {
            System.out.println(key + " --> " + map.get(key));
        }
        
        System.out.println("--- entrySet ---");
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        
        for (Map.Entry<String,Integer> entry: entrySet) {
            System.out.println(entry.getKey() + " --> " + entry.getValue());
        }
    }
}
// The comparator supports null comparison.
class StringNullComparator implements Comparator<String> {

    @Override
    public int compare(String o1, String o2) {
        if(o1 == o2) {
            return 0; // o1 = o2
        }
        if(o1 == null)  {
            return -1; // o1 < o2
        }
        if(o2 == null)  {
            return 1; // o1 > o2
        }
        return o1.compareTo(o2);
    }
}
Output:
--- keySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400
--- entrySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400

Java Collections Framework Tutorials

Show More

Newest Articles

Show More