TreeMap in Java

Introduction to Java TreeMap

A TreeMap is similar to an ordinary HashMap except for the fact that it stores the key-value pairs in the natural sorting order of the keys, i.e., the non-decreasing order. Alternatively, we can also define our own sorting order with the help of a Comparator.

Features of a TreeMap

• TreeMap in Java is a part of the Java Collection framework where it implements the Map interface and NavigableMap as well. It extends AbstractMap class.
• It doesn't allow null keys (like Map). However, there can be multiple null values in a TreeMap. It throws NullPointerException in the case of any null key insertion.
• It stores the key-value pairs in the natural sorting order of the keys or a sorting order defined with the help of a Comparator.
• TreeMap is not synchronized. To get a synchronized version of the TreeMap, we can use Collections.synchronizedSortedMap method.

Declaration

NavigableMap, being an interface, cannot have any objects created with it. So, it has to be implemented with the abstract class, AbstractMap which provides the implementation of the Map interface. Now, since AbstractMap is an abstract class, TreeMap extends AbstractMap to create objects.

Parameters

TreeMap is represented as TreeMap<K, V> where:

• K stands for key and can be of any type
• V stands for the corresponding value for a key

Internal Working of TreeMap in Java

TreeMap internally uses a Red-Black tree, a self-balancing binary search tree containing an extra bit for the color (either red or black). The sole purpose of the colors is to make sure at every step of insertion and removal that the tree remains balanced. 

For a red-black tree,

• the nodes must be red or black.
• the root node must be black in color.
• each and every path from the root node to a null should consist of the same number of black nodes.
• Any red node cannot have another red node as its neighbor.

Let's take up an example where we would insert the following key-value mappings into the TreeMap and see what happens behind the scenes.

We have the first key-value mapping as (key: 3, value: John) and this mapping will be considered the root of the TreeMap construction. Here's what the structure of the TreeMap looks like.

Since it is kind of a binary search tree, so it will consist of left and right pointers, where the keys lower than the parent will be put as the left child and the ones greater than the parent will be put as the right child.

The second key-value mapping (key: 1, value: Alex) is lower than the root key. Therefore, it will be placed as the left child of the root element. Also, this key-value mapping will currently have its left and right pointers as null.

The third key-value mapping (key: 4, value: Chris) has its key greater than the root key and will be placed as the right child of the root element. It will have left and right pointers as null.

When the fourth key-value mapping (key: 5, value: Marsh) is inserted into the TreeMap, it is greater than the root element and also greater than the succeeding child of the root element (key: 4, value: Chris). So, it will be placed as the right child of the mapping with key 4. The right pointer of the mapping with key 4 will now be pointing to the current key-value mapping.

Finally, the last key-value mapping (key: 2, value: Tim) is lower than the root key but also greater than the left child of the root key, i.e. (key: 1, value: Alex). Then, it must be placed as the right child of the key-value mapping with key 1. Here's the final structure of the TreeMap.

The figure below shows the final tree with just the keys.

The order of the tree will be an inorder traversal, i.e. 1, 2, 3, 4, 5.

Constructors of Java TreeMap

There are four ways to define the constructor for a TreeMap. These constructors define how the objects will be created in order to be inserted into the TreeMap. They are listed below.

• TreeMap()
• TreeMap(Comparator comp)
• TreeMap(Map M)
• TreeMap(SortedMap sm)

TreeMap()

This method involves a default constructor where we can simply put the key-value pairs in any order and the output will be sorted based on the natural sorting order of the keys. You can set your keys as double, integer, String, etc., and they will be eventually sorted in non-decreasing order.

Let's take up an example of employees in a department. Each of these employees will be having an id that will help us sort them in non-decreasing order. So, their id will be considered as a key (integer) and their names as the corresponding values (String).

Output:

With the help of the default constructor, we can see that the key-value mappings have been sorted in the non-decreasing order of the keys.

TreeMap(Comparator)

Let's say we need to sort the employees based on the flexographic decreasing order of their names. In this case, the natural sorting order cannot be our choice, we need to go for Comparator which would help us implement our own sorting order.

Let's take up the same example, but now, the names will be the keys while their id will be the corresponding values. The output should be based on the descending order of the names.

Output:

The class CustomComparator makes use of the Comparator class and uses its compare() method to compare the two objects. We have written the return statement in the compare() method in a way that it would return first the element having the value greater than the other.

TreeMap(Map)

What if we already have a map with the randomly stored key-value pairs? We can create another TreeMap that takes up all the entries from a map and stores them based on a sorting order.

Output:

In the above example, the HashMap has been passed as an argument to the TreeMap that would sort all the key-value mappings from the HashMap in the sorted order of the keys.

TreeMap(SortedMap)

SortedMap is a child interface of the Map and it has to be implemented with the help of a class. Therefore, TreeMap comes into the picture. 

SortedMap also provides additional methods such as:

• Comparator comparator()
• Object firstKey();
• Object lastKey();
• SortedMap headMap (Object beforeThisKey)
• SortedMap tailMap (Object fromThisKey)
• SortedMap tailMap (Object fromThisKey, Object beforeThisKey)

Output:

Since we used the SortedMap interface in the above example, we have different methods to access a map that contains elements equal to or less than the original map.

Methods of Java TreeMap Class

Operations on TreeMap

Insert Elements to TreeMap

We can insert the key-value pairs in TreeMap with the put() method where each of the entries will be compared and stored in the sorted order of the keys.

Output:

Access TreeMap Elements

Accessing a specific value from its associated key can be done with the help of the get() method. Also, if we need to have a set view of all the keys in the map, then the keySet() method should be called. Similarly, for a set view of entry (key-value mappings), the entrySet() method will be called.

Output:

Removing Element

remove(Object key) removes and returns the given key-value mapping with the specified key if it is present in the TreeMap. If the specified key is not present, then the remove() method doesn't return anything.

Suppose if we need to remove Chris, so his id will be needed to remove it from the TreeMap.

Output:

Iterating Through the TreeMap

To iterate all the elements (key-value mappings) in the TreeMap, the enhanced for loop iterates through each element. Since each of the elements is a part of the Entry interface and eventually exists inside the Map interface, we'll have to denote them as Map.Entry while iterating inside the enhanced for loop.

Output:

Replace TreeMap Elements

To replace the existing values mapped to any key, we can simply make use of the put(Object key, Object value) method where the previous value will be replaced with the new one.

In our example, let's change the name of the employee with id 5 to Annie, so the previous value, Chris will now be changed to Annie.

Output:

Methods for Navigation

The TreeMap also implements NavigableMap which provides several direct methods to access the elements of a treemap. Due to NavigableMap, we can find the first and last keys as well as entries. Moreover, the ceiling and floor keys and values can also be found with the help of NavigableMap implementation.

Let's look at each of these examples.

First and Last Elements

• firstKey() will return the first key in a treemap.
• lastKey() will return the last key in a treemap
• Similarly, firstEntry() will return the first entry in a treemap and lastEntry() will return the last entry in a treemap.

Output:

Ceiling, Floor, Higher and Lower Elements

• higherKey() returns the key that is just greater than the specified key.
• higherEntry() returns the entry that has its key just greater than the specified key.
• Similarly, lowerKey() returns the key which is the greatest among all the keys lower than the given key and the same applies to the lowerEntry().
• On the contrary, ceilingKey() is meant to yield a key that is the least great than the mentioned key. If any key passed as an argument actually exists in the mao, then this key will be returned as the output.
• ceilingEntry() method returns an entry with the key that is lowest among the entries with keys greater than the key of the given entry. If the entry passed as the argument has the key actually present in the map, the same entry would be returned.
• floorKey() method will return the key that is greatest among the keys lower than the given key. Again, if the key specified is actually present in the map, then it would be returned as the output.
• floorEntry() method returns an entry with the key that is greatest among the entries with a key lower than the given entry's key. If the entry passed as the argument has the key actually present in the map, the same entry would be returned.

Output:

TreeMap Comparator

When the natural sorting order doesn't sound to be a possible alternative, then we can define our custom sorting order by implementing the Comparator class. We can do so by creating a class that implements the Comparator class and uses compare method to return the objects in the desired order.

The compareTo() method returns a value that will either be greater than, less than, or equal to 0. If the value > 0, then obj1 will be put first in the sorting order. If the value < 0, then the obj2 will come before obj1 in the sorting order. If the value is equal to 0, then their order will the same as it was.

What is the Difference Between HashMap and TreeMap?