Internal Implementation of TreeMap in Java

      We learned the internal working of HashMap in post of How HashMap works internally.  In this post, we can discuss about the internal working of TreeMap in Java.

What is TreeMap ? 

    TreeMap class is a like HashMap which stores a key-value pairs. The major difference is that TreeMap sorts the key in ascending order.

   TreeMap is sorted according to the natural ordering of it's keys, or by a Comparator provided at map creation time, depending on which constructor is used. There are mainly two types of
constructor in TreeMap, 

         TreeMap();
         TreeMap(Comparator comp);

How TreeMap works internally ?

         TreeMap is Red-Black tree based NavigableMap implementation. In other words, it sorts the TreeMap object keys using Red-Black tree algorithm.

Red-Black Tree algorithm:--

       Red-Black tree is a self balancing Binary Search Tree(BST) where every node follows some rules,

• Every node has color either Red or Black.
• Root of tree is always black.
• There are no two adjacent red nodes.

• Every path from root to a null node has same number of black nodes.  

Red-Black Tree

          Time Complexity of TreeMap of search i.e  get, put and remove is O(log n) . 
         Being a self balancing, we keep inserting and deleting entries, tree growing longer on one edge or shorter on the other side.
         This would mean that an operation would take a shorter time on the shorter branch and longer time on the other branch which is furthest from the root, something we would not want to happen. Therefore this is taken care of in the design of Red-Black trees.

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