Tag: internal working of treemap in java

TreeMap is another implementation of the Map interface like HashMap and HashTable.Only difference is that it sorts keys in the order of the ascending order.

TreeMap is sorted as per the natural ordering of its keys, by Inbuild Comparable implementation or by a Comparator provided at map creation time which will depend on which constructor was used when instantiating.

Let’s look at some different Map Constructors.

TreeMap() :As known it constructs an empty TreeMap.

TreeMap(Map map): It creates a TreeMap with the entries from another map.

TreeMap(Comparator compare): It takes an Comparator object and on the basis of that it sorts the keys.

TreeMap(SortedMap sortedMap): It populates the TreeMap instance with the entries from the sortedMap.

Internally it is implemented using a Red Black Tree.

As many of you know, in a tree data structure the left node is smaller than the parent and right node is bigger than the parent in value.

Let’s look at the characteristics of the Red Black Tree.

• In a red black tree, the color of the node is either a red or black.
• The root node is always black in color.
• The red color node cannot have a neighbor node of the same color.
• The number of black nodes from Root to Null should be same.

So you can say a Red Black Tree is a Balanced Tree and it is an kind of ideal data structure for sorting.

Let’s look at the code implementation of the TreeMap.

import java.util.Iterator;
import java.util.TreeMap;
 
public class TreeMapExample 
{
    public static void main(String[] args) 
    {
        TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
         
        tm.put(2,  "John" );
        tm.put(1,  "James");
        tm.put(3,  "Glen");
        tm.put(4,  "Matt");
         
        System.out.println(tm);
    }
}

O/P:
{1=James, 2=John, 3=Glen, 4=Matt}

Now let’s take a look into an example with an compaartor for an user object.

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

public class TreeMapComparator {

	public static void main(String a[]){
		TreeMap<Employee,String> tm = new TreeMap<Employee, String>();

		tm.put(new Employee("John",10000), "John");
		tm.put(new Employee("Mike",5000), "Mike");
		tm.put(new Employee("Glen",2000), "Glen");
		tm.put(new Employee("Matt",5000), "Matt");

		Set<Employee> ks = tm.keySet();
         	System.out.println("Without Comparator");

		for(Employee emp:ks){
			System.out.println("Salary is "+emp.getSalary()+" For "+tm.get(emp));
		}

		System.out.println("With Comparator for sorting on the basis of Salary");

		TreeMap<Employee,String> tm1 = new TreeMap<Employee, String>(new EmpSalComp());

		tm1.put(new Employee("John",10000), "John");
		tm1.put(new Employee("Mike",5000), "Mike");
		tm1.put(new Employee("Glen",2000), "Glen");
		tm1.put(new Employee("Matt",5000), "Matt");

		Set<Employee> ks1 = tm1.keySet();

		for(Employee emp:ks1){
			System.out.println("Salary is "+emp.getSalary()+" For "+tm1.get(emp));
		}
	}
}

//Define the Employee class POJO for which sorting would be done using comparator
class Employee{
	
	private String empName;
	private int salary;
	
	public Employee(String empName, int salary){
		this.empName = empName;
		this.salary = salary;
	}
	
	public String getName() {
		return empName;
	}
	public void setName(String empName) {
		this.empName = empName;
	}
	public int getSalary() {
		return salary;
	}
	public void setSalary(int salary) {
		this.salary = salary;
	}
	public String toString(){
		return "Name = "+this.empName+" & Salary = "+this.salary;
	}
}

class EmpSalComp implements Comparator<Employee>{

	@Override
	public int compare(Employee e1, Employee e2) {
		if(e1.getSalary() > e2.getSalary()){
			return 1;
		} else {
			return -1;
		}
	}
}

O/P:

Without Comparator
Salary is 10000 For John
Salary is 5000 For Mike
Salary is 2000 For Glen
Salary is 5000 For Matt
With Comparator for sorting on the basis of Salary
Salary is 2000 For Glen
Salary is 5000 For Mike
Salary is 5000 For Matt
Salary is 10000 For John