Explaining TreeMap in Java in Simple English

TreeMap in Java, just like the HashMap, is part of the java collection framework. It is a red-black tree-based implementation of the Map interface, NavigableMap, and AbstractMap classes. It stores data in the form of Key and Value pairs where the key is a unique identifier used to associate each value on the Map. It means that every key is mapped to exactly one value and that we can use it to retrieve its corresponding value from the map. 

Now that we have a general idea about TreeMap, Let’s dive into its more advanced features for a better understanding.

Index

What is a TreeMap?

As mentioned above, TreeMap is nothing more than a Data Structure that stores data in the form of the key and value pair, where the key should be a unique identifier that allows us to perform multiple operations like add, delete, replace, etc on the data stored in the TreeMap.

Unlike HashMap which only takes a constant time, it takes a logarithmic time to perform the above-mentioned operations. This makes one wonder why it was introduced in the first place. The answer is simple…to save the memory used to store data. It only uses the amount of memory needed to hold/ store the items, unlike a HashMap which uses a contiguous region of memory.

The best thing about TreeMap is that here storing of data is done based on the natural ordering of keys – if keys are initialized as integers then they will be stored in ascending order of the keys, and if the keys are initiated as String or characters, then the data will be stored in the alphabetic order.

But in the case of TreeMap custom sorting is also possible. For that, we have to use a specific type of constructor to perform this custom sort which we will see later in the blog. 

The ordering maintained by a TreeMap (just like any other sorted map) must be compatible with the equal sign if it correctly wants to implement the Map interface irrespective of whether a constructor is provided or not. This is because all the operations performed on the map Interface use the equal operator, while all the operations performed on the Sorted map use its compareTo or compare method.

Initializing a TreeMap

Creating a TreeMap is the same as creating a HashMap in Java. Just like in HashMap, first, we have to import the TreeMap class from the util package and then write the following line to create a new TreeMap in Java and use all its methods and constructor.

TreeMap<Key, Value> numbers = new TreeMap<>()

Here

key – is the unique identifier used to associate each element in the map

value – elements associated by keys in a map.

In the above code, we have created a new TreeMap named numbers which will follow the natural ordering of sorting as we have not specified any type of constructor for it to perform sorting based on that constructor. let’s take an example to understand.

import java.util.*;    
public class Main  
{    
    public static void main(String args[])  
    {    
//object of TreeMap class  
        TreeMap<String,String> treemap=new TreeMap<String,String>();      
//we can take anything in the key such as integer, string, etc.  
//adding elements to the TreeMap  
        treemap.put("H","Ahmedabad ");      
        treemap.put("D","Jaipur");      
        treemap.put("B","Delhi");      
        treemap.put("F","Agra");   
        treemap.put("P","Patna");  
//Printing values
        System.out.println("Original TreeMap");
        System.out.println(treemap);            
    }    
}  

Features of TreeMap

1. It can only contain unique elements
2. It cannot have null keys but can have multiple null values. This is because the compareTo() or the compare() method throws a NullPointerException when encountered by a null key.

If we are using a comparator for custom sorting as told above, then it depends on the implementation of the compare() method on how null values get handled.

1. Entry pairs returned by the methods and their views represent snapshots of mappings at the time they were produced. Thus do not support the Entry.setValue method.
2. It takes logarithmic time complexity to complete simple operations like add, remove, containKey, etc which when compared to HashMap is slower.
3. It is not thread-safe – if multiple threads of data are passing from it concurrently, then at least one of those threads will be able to change that map structurally – simply said it will be able to change its structure.
4. Unlike HashMap, TreeMap stores its data in a Self Balancing Binary Search Tree.
5. In this elements are sorted in a natural way – in ascending order unless otherwise stated.
6. Unlike HashMap, TreeMap will only take the amount of memory needed to store data.
7. Due to its no memory limitation, we can store as much data as we want in it.

Why is TreeMap not Synchronized in Nature?

By default, it is unsynchronised. What it means is that if multiple threads of data are passing from it concurrently, then at least one of those threads will be able to change that map structurally – simply said it will be able to change its structure.

One thing to note here as per the official documentation of Oracle, “A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with an existing key is not a structural modification.”

This issue can only be solved by somehow synchronizing it externally by either synchronizing some object that naturally encapsulates the map or by wrapping the complete map using the Collections.synchronizedSortedMap method. The latter method is considered to be the best of the two and can even be implemented at the time of map creation and can prevent accidental unsynchronised access to the map.

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(…)); 

Internal Structure of TreeMap.

As we know that in TreeMap the data gets stored in a tree data structure, and a node of a tree data structure has 3 reference elements – parent, right, and left. 

Where

• The left element will always be less than the parent element.
• The right element will always be greater than or equal to the parent element.
• The logical comparison of the objects is done by natural order.

Basic Operations of TreeMap.

Add Elements in TreeMap

Just like in the HashMap, we have to use the put() method to add an element in the TreeMap. But, the insertion order will not be the same as the order we inserted the elements. This is because TreeMap allows the natural ordering of elements which is again done in ascending order if the elements are numbers and in alphabetic order if the elements are in the form of alphabets.

We have already seen how the put() method is used in the basic example of TreeMap

Deleting / Removing Elements from TreeMap

There are two ways of removing or deleting an element from the TreeMap.

• remove(key) – removes the mapping associated with the specified key. 
• remove(key, value) – removes the entry from the map only if the specified key is associated with the specified value and returns a boolean value

import java.util.*;    
public class Main  
{    
public static void main(String args[])  
{    
//object of TreeMap class  
    TreeMap<String,String> treemap=new TreeMap<String,String>();      
//we can take anything in the key such as integer, string, etc.  
//adding elements to the TreeMap  
    System.out.println("Original TreeMap");
    treemap.put("H","Ahmedabad ");      
    treemap.put("D","Jaipur");      
    treemap.put("B","Delhi");      
    treemap.put("F","Agra");   
    treemap.put("P","Patna");  

   //Printing values
    System.out.println(treemap);
  
  // Removing the element corresponding to key
      treemap.remove("F");
  
    // Printing the updated elements of Map
    System.out.println();
    System.out.println("Updated TreeMap");
    System.out.println(treemap);    
    }    
}  

Changing an element in TreeMap

Just like with HashMap, we can change the element by adding a new element with a key that is already a part of the TreeMap. This will update the value of that key by replacing the old value with the new one that we have just inserted.

For this, we will be using replace(key, value) method. But again there are several other methods of replacing an element from a TreeMap. They include replace(key, old, new) and replaceAll(function).

• replace(key, old, new) – same as the above method, but the only difference is here we have also specified the value that we have to replace. 
• replaceAll(function) – replaces each value of the map with the result of the specified function

import java.util.*;    
public class Main  
{    
public static void main(String args[])  
{    
//object of TreeMap class  
    TreeMap<String,String> treemap=new TreeMap<String,String>();      
//we can take anything in the key such as integer, string, etc.  
//adding elements to the TreeMap  
    System.out.println("Original TreeMap");
    treemap.put("H","Ahmedabad ");      
    treemap.put("D","Jaipur");      
    treemap.put("B","Delhi");      
    treemap.put("F","Agra");   
    treemap.put("P","Patna");  

//Printing values  
    System.out.println(treemap);
  
// Inserting the element at specified corresponding to specified key
    treemap.put("F", "Goa");
  
    // Printing the updated elements of Map
    System.out.println();
    System.out.println("Updated TreeMap");
    System.out.println(treemap);    
    }    
}  

Iterating through the TreeMap

Well, there are multiple ways using which we can iterate over a TreeMap, among them the most famous one, and the one we will be using to explain will be the for-each loop.

import java.util.*;    
public class Main  
{    
    public static void main(String args[])  
    {    
//object of TreeMap class  
        TreeMap<String,String> treemap=new TreeMap<String,String>();      
//we can take anything in the key such as integer, string, etc.  
//adding elements to the TreeMap  
        treemap.put("H","Ahmedabad ");      
        treemap.put("D","Jaipur");      
        treemap.put("B","Delhi");      
        treemap.put("F","Agra");   
        treemap.put("P","Patna");  
//for-each loop for fetching the elements from the TreeMap  
        for(Map.Entry m:treemap.entrySet())  
        {      
//prints the key and value pair of the elements   
            System.out.println(m.getKey()+" "+m.getValue());      
        }      
    }    
}  

In the above code, we have used a method to access all the key value mappings and print them using the for each loop. This method is generally used to create a set out of the same elements contained in the treemap.

Well, there are two more that we can use but their functionality is a little different.

• keySet() – returns a set of all the keys of a tree map
• values() – returns a set of all the maps of a tree map

Some more Methods of TreeMap in Java

Constructors in TreeMap 

We need to create an object to construct any type of class from the map interface and TreeMap is not an exception. The TreeMap class consists of four constructors. They are – 

1. TreeMap()
2. TreeMap(Comparator comp)
3. TreeMap(Map M)
4. TreeMap(SortedMap sm)

Sorting in TreeMap

We already know that in TreeMap, data is sorted and stored based on the increasing order of their keys irrespective of their data type. What it means is that if the keys are initialized as Integers, the data will be sorted in the increasing order of their keys, but if they are initialized as alphabets, they will be sorted and stored alphabetically. 

Let’s see an example to understand this.

import java.util.*;    
public class Main  
{    
    public static void main(String args[])  
    {    
//object of TreeMap class  
        TreeMap<String,String> treemap=new TreeMap<String,String>();      
//we can take anything in the key such as integer, string, etc.  
//adding elements to the TreeMap  
        treemap.put("H","Ahmedabad ");      
        treemap.put("D","Jaipur");      
        treemap.put("B","Delhi");      
        treemap.put("F","Agra");   
        treemap.put("P","Patna");  
//Printing values
        System.out.println("Original TreeMap");
        System.out.println(treemap);            
    }    
}  

The natural way of doing things is good but sometimes we want data to be sorted in a different order or displayed in a different way rather than storing and displaying in ascending order we want that order to be descending.

In TreeMap we can easily achieve this using the concept of custom sorting which we have already seen a glimpse of it in the above sections. To perform custom sorting we just have to use any comparator other than the Basic one. It will be better to understand this with the help of an example in which we have printed the TreeMap in the reverse order – descending order of keys.

import java.util.*;    
public class Main  
{    
    public static void main(String args[])  
    {    
//object of TreeMap class  
        TreeMap<String,String> treemap=
        new TreeMap<String,String>(Comparator.reverseOrder());      
//we can take anything in the key such as integer, string, etc.  
//adding elements to the TreeMap  
        treemap.put("H","Ahmedabad ");      
        treemap.put("D","Jaipur");      
        treemap.put("B","Delhi");      
        treemap.put("F","Agra");   
        treemap.put("P","Patna");  
//Printing values
        System.out.println("Updated TreeMap");
        System.out.println(treemap);            
    }    
}  

Internal Working of TreeMap

As we already know, in TreeMap, the sorting of data is based on their natural ordering of keys – in ascending order for integers and alphabetical order for strings, and these sorted data are stored in a Self Balancing Binary Search Tree or Red Black Tree. To understand the internal working of the Treemap, we first have to understand the Red Black Tree Algorithm.

Red-Black Tree Algorithm

A red-black tree is a self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the color red or black. These colors are used to ensure that the tree remains balanced during the insertions and deletions process. 

Although the balance of the tree is not perfect, it is good enough to reduce the searching time and maintain it around O(log n) time, where n is the total number of elements in the tree. It must be noted that as each node requires only 1 bit of space to store the color information, these types of trees show an identical memory footprint to the classic (uncolored) binary search tree. 

There are some points that we need to know about Red Black Tree before starting our main topic – how TreeMap works internally.

1. As the name suggests, it is a BST with colored nodes.
2. The root node will always be black.
3. The red node can not have red color children nodes.
4. All paths from the root node to the null should consist of the same number of black nodes.
5. All leaves will be black.

Let’s understand the meaning of Self Balancing BST here. Imagine a situation where one side of the tree continues to grow longer and longer as we insert more elements into it while the other part keeps getting shorter and shorter as we keep on deleting items.

This would mean that an operation would take a shorter time on the shorter branch and a longer time on the branch which is furthest from the root, something we don’t want.

Therefore, this is taken care of in the design of red-black trees. For every insertion and deletion, the maximum height of the tree on any edge is maintained at O(log n) i.e. the tree balances itself continuously.

Step-by-Step Procedure for Working on TreeMap

Let’s see a code of TreeMap and with the help of that code, we will understand the internal working of TreeMap.

import java.util.*;    
public class Main  
{    
    public static void main(String args[])  
    {    
//object of TreeMap class  
        TreeMap<String,String> treemap=new TreeMap<String,String>();      
//we can take anything in the key such as integer, string, etc.  
//adding elements to the TreeMap  
        treemap.put("H","Ahmedabad ");      
        treemap.put("D","Jaipur");      
        treemap.put("B","Delhi");      
        treemap.put("F","Agra");   
        treemap.put("P","Patna");  
//for-each loop for fetching the elements from the TreeMap  
        for(Map.Entry m:treemap.entrySet())  
        {      
//prints the key and value pair of the elements   
            System.out.println(m.getKey()+" "+m.getValue());      
        }      
    }    
}  

As you can see in the above code, we have added some data in the form of key and value pairs where both are in the form of Strings and thus will be sorted alphabetically. Thus the output will be – 

Let’s see a visual interpretation of the TreeMap which has been created using the above code.

Adding the First Element in the TreeMap

We have seen in the above section of this blog that to add a node or data in the TreeMap we have to use the put method. Thus 

treemap.put(“H”,”Ahmedabad “);

In the above code, ‘H’ is the key and ‘Ahemdavad’ is the value. This data will become the root node of our TreeMap and the rest of the data will be attached to it depending on whether the value of its key is smaller or greater than the root.

Adding the Second Element in the TreeMap

Just like the first element, we will use the put method to insert the second element which will be either on the left side of the root node or the right depending upon whether the key of the second element is smaller than the key of the root node or not 

treemap.put(“D”,”Jaipur”);      

From the above code, we can say that ’D’ is smaller than ‘H’. Thus it will go on the left side of the root node

Adding the Third Element in the TreeMap

Just like the first two elements, we will use the put method to add the third element in the TreeMap and compare its key value with the root’s key value to determine its location. If its key value is greater than the root’s, then it will go on its right side but if its value is less than the root’s value, then we have to follow the same procedure with the first element considering it the root element.

The third node which will be added to the TreeMap is – 

treemap.put(“B”, “Delhi”);      

According to our alphabets, B is smaller than D which in turn makes it smaller than H, Thus it has been placed on the left-hand side of the element with key ‘D’. This is because in this case the first element is considered the root element for the rest of the tree.

Adding Forth Element in the TreeMap

Like the first three elements, we add the fourth element in this TreeMap by just checking its key value.

treemap.put(“F”,”Agra”);  

The key value of the fourth element is ‘F’ which is greater than ‘D’ but smaller than ‘H’. So, it will be placed on the left side of H but on the right side of D.

Adding Fifth Element in the TreeMap

Similarly, the fifth element will be added on the right side of the root element ‘H’ as ‘P’ is greater than ‘H’ in alphabetical order.

treemap.put(“P”,”Patna”);  

After inserting all the elements in the TreeMap, it will look something like this – 

Conclusion

In this article, we have learned that TreeMap is also a part of the map interface just like HashMap, and stores data in the form of key and value pairs, but stores it in the form of a Self Balancing Binary Search Tree – Red Black Tree. 

It is unsynchronised and sorts data naturally in ascending order of either number or alphabets depending upon the type of data type we are using to declare the keys as it sorts and stores data according to its keys. We can also do some custom sorting using a comparator while initializing a TreeMap Just like other Sorted Maps, TreeMap also allows us to perform some operations like add, delete, replace, etc with its inbuilt methods.

Due to its natural way of sorting data, the time complexity for these operations is log n which makes it slower than a HashMap in terms of accessing data and speed, but when it comes to storage it has a better tendency to store data than HashMap as HashMap’s stores’ data in a contiguous order (it stores data in an array) while TreeMap stores data in a self-balancing binary search tree in which we can as much data as we want as it only takes the required amount of space needed to store the data.

Frequently Asked Question

What is TreeMap in Java?

The TreeMap in Java is used to implement the Map interface and NavigableMap along with the AbstractMap Class. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.