Internal Implementation of TreeMap in Java

       We learned about the internal working of HashMap in the post How HashMap Works Internally. In this post, we will discuss the internal working of TreeMap in Java

What is TreeMap ? 

    The TreeMap class is similar to HashMap as it stores key-value pairs. The key difference is that TreeMap maintains the keys in ascending order.

A TreeMap is sorted either according to the natural ordering of its keys or by a Comparator provided at the time of map creation, depending on the constructor used. 

There are primarily two types of constructors in TreeMap,

         TreeMap();
         TreeMap(Comparator comp);

How TreeMap works internally ?

         TreeMap is a Red-Black Tree–based implementation of the NavigableMap interface. In other words, it sorts the keys of a TreeMap using the Red-Black Tree algorithm.

Red-Black Tree Algorithm:

A Red-Black Tree is a self-balancing Binary Search Tree (BST) in which every node follows specific rules:

• Each node is either red or black.

• The root of the tree is always black.

• No two adjacent nodes can both be red.

• Every path from the root to a null node must have the same number of black node.

Red-Black Tree

           In TreeMap, the time complexity of get, put, and remove operations is O(log n). This is achieved using a Red-Black Tree, which maintains balance during insertions and deletions to prevent skewed structures.

TreeMap Examples :

Simple String as key example,

package com.test;

import java.util.Map;
import java.util.TreeMap;

public class TreeMapEx {
    public static void main(String[] args) {
         TreeMap<String, Integer> treeMap = new TreeMap<String, Integer>();
         treeMap.put("Mahesh", 1);
         treeMap.put("Anil", 9);
         treeMap.put("John", 3);
         for(Map.Entry<String, Integer> map : treeMap.entrySet()) {
              System.out.println(map.getKey());
         }
    }

}

Output :-- Anil

           John

           Mahesh

 

Example to sort keys in TreeMap using Comparator with custom object.

package com.test;

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

public class TreeMapSorting {
      public static void main(String[] args) {
           TreeMap<Employee, String> treeMap = new TreeMap<Employee, String>(new MyNameComp());
           treeMap.put(new Employee(10,  "Anil"), "one");
           treeMap.put(new Employee(10,  "Mahesh"), "two");
           treeMap.put(new Employee(10,  "John"), "three");
           treeMap.put(new Employee(10,  "Nagesh"), "four");
           for (Map.Entry<Employee, String> map : treeMap.entrySet()) {
                   System.out.println("Key : ("+map.getKey()+ "), Value : "+ map.getValue());
           }
      }
}
 

class Employee {
      private Integer id;
      private String name;
      public Employee(Integer id, String name) {
           this.id = id;
           this.name = name;
      }
      public Integer getId() {
           return id;
      }
      public void setId(Integer id) {
           this.id = id;
      }
      public String getName() {
           return name;
      }
      public void setName(String name) {
           this.name = name;
      }
      public String toString() {
           return this.name+":"+id;
      }
}

class MyNameComp implements Comparator<Employee> {

        public int compare(Employee o1, Employee o2) {
               return o1.getName().compareTo(o2.getName());
        }
 
}

Output :--  

Key : (Anil:10), Value : one
Key : (John:10), Value : three
Key : (Mahesh:10), Value : two
Key : (Nagesh:10), Value : four 

Related Posts:-- 
1) How HashMap works internally in Java? 
2) Internal implementation of ArrayList in Java  
3) Collection Related Interview Questions and Answers in Java(List,Map & Set)
4) Internal Implementation of LinkedList in Java 
5) Difference between Loose Coupling and Tight Coupling in Java With Examples.
6) String Interview Questions and Answers 
7) Factory Design Pattern in Java