Understanding TreeMap

A TreeMap is an implementation of the Map interface. It is a member of the Java Collection Framework and is used to store key-value pairs. Unlike HashMap, it is used to store key-value pairs in sorted order of their keys.


Red-Black Tree

TreeMap sorts the key objects using Red-Black tree algorithm. A Red-Black tree is a complex algorithm. It is a special type of binary search tree with each node having extra information about its color. Shown below are the properties of a Red-Black tree.

  • A node can be either red or black.
  • The root node should be black.
  • All leaf nodes should be black.
  • Each red node must have two black children nodes and no other children nodes.
  • All possible paths from a given node to a leaf node should contain equal number of black nodes.

To know more about Red-Black tree algorithm click here.


TreeMap's Entry object

Each node in the Red-Black tree stores a key-value pair. These key and value objects are put inside an Entry object and this object serves as nodes of the Red-Black tree. For the entry object to be used as a Red-Black tree node, it needs to store some more information about its neighbour nodes, parent node and its color. Shown below are the fields of an Entry object of TreeMap.

static final class  Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left = null;
    Entry<K,V> right = null; 
    Entry<K,V> parent; 
    boolean color = BLACK;

    ...  ... ...
}

Sorting with Comparator/ Comparable

TreeMap uses a Comparator to sort the key object, the comparator object can be assigned to it by its constructor shown below.

    private final Comparator<? super K> comparator;

    public  TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

If the comparator is not provided, it uses the natural ordering of the key objects to do the sorting.

Natural ordering’ is the ordering implied by the implementation of the Comparable interface by the objects used as keys in the TreeMap. Hence, if the comparator is not used, the objects to be used as key in the TreeMap should implement Comparable interface.

The Comparator interface defines a compare(object1, object2) method. The method is used to compare two objects and returns a negative value, 0 or a positive value if the first argument is less than, equal to or greater than the second argument.

The Comparable interface defines a compareTo(object) method. The method is used to compare the object itself with another object and returns a negative value, 0 or a positive value if the object is less than, equal to or greater than the object in the argument.

Shown below is the put() method of TreeMap. Here it first creates the root node of the Red-Black tree if it's empty. It next uses the comparator if it's present, else it uses the key object's natural ordering.

public V put(K key, V value) {
    Entry<K,V> t = root;
	/***  Create root node if empty  ***/	
        if (t == null) {
            root = new Entry<K,V>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }

        int cmp;
        Entry<K,V> parent;
        Comparator<? super K> cpr = comparator;
		
	/***  Use comparator if present  ***/	
        if (cpr != null) {
    	    do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
              } while (t != null);
         }
		 
	 /***  Use natural ordering / Comparable interface  ***/	
         else {
		if (key == null)
                    throw new NullPointerException();
                Comparable<? super K> k = (Comparable<? super K>) key;
                do {
                    parent = t;
                    cmp = k.compareTo(t.key);
                    if (cmp < 0)
                        t = t.left;
                    else if (cmp > 0)
                        t = t.right;
                    else
                        return t.setValue(value);
                } while (t != null);
            }
			
			/***  Create entry object and insert to the tree  ***/
            Entry<K,V> e = new Entry<K,V>(key, value, parent);
            if (cmp < 0)
                parent.left = e;
            else
                parent.right = e;
            fixAfterInsertion(e);
            size++;
            modCount++;
            return null;
}

The TreeMap uses compare/compareTo method to sort the key objects.If two objects are considered to be equal by the compare/compareTo method of the Comparator/ Comparable interface, the object compared will not be stored in the TreeMap. This is how a TreeMap only store unique entries and does not allow duplicate keys.

Using null keys

The null keys are not permitted if natural ordering is used in the TreeMap. We can see this in the put() method shown above. It throws a NullPointerException if key is null in case of natural ordering. When a Comparator is used, the null keys can be used if the Comparator permits its usage.


Sample Code

Shown below is the Customer class that we will use as key in the TreeMap. It has two property name and email. The Customer class implements the Comparable interface, thus overrides the compareTo() method. We use the name to compare the object. If the names are found to be equal, we consider the objects are equal hence return 0 from compareTo()

public class Customer implements Comparable{
	
    private String emailId;
    private String name;
	
    public Customer(String email, String name){
	this.name = name;
	this.emailId = email;
    }
	
    public String getEmailId() {
	return emailId;
    }
	
    public String getName() {
	return name;
    }

    @Override
    public int compareTo(Customer obj) {
		
	if(this.name.equals(obj.getName()))
		return 0;
	else
		return this.name.length() - obj.getName().length();
    }
}

Shown below is our Comparator which we will pass to the TreeMap. Its compare() method below compares the emailId, unlike the Customer's compareTo() method. If emailIds are equal, we consider the objects as equal.

public class CustomerComparator implements Comparator{

    @Override
    public int compare(Customer o1, Customer o2) {
		
	if(o1.getEmailId().equals(o2.getEmailId()))
	    return 0;
	else
    	    return o1.getEmailId().length() - o2.getEmailId().length();
    }	
}

Main class below creates two customer objects and adds it to a TreeMap. The TreeMap is also provided with our Comparator object; hence it uses the comparator and ignore the natural ordering of the Customer. The size() method would produce "2" since the emailId's of the two objects are different.

public class Main {
    public static void main(String[] args) {
	SortedMap<Customer, String> sortedMap = new TreeMap<Customer, String>(new CustomerComparator());
	Customer c1 = new Customer("[email protected]", "Employee 1");
	Customer c2 = new Customer("[email protected]", "Employee 1");
	sortedMap.put(c1, c1.getName());
	sortedMap.put(c2, c2.getName());
		
	System.out.println(sortedMap.size());    // Prints 2
    }
}

Shown next is a modified version of the Main class where we have ignored the Comparator. Hence the natural ordering of the Customer object will be used. The size() method here prints "1", since we use the name property of Customer to compare the objects. As both the customer objects have same name, they are considered to be equal and hence only one of them is stored in the TreeMap.

public class Main {
    public static void main(String[] args) {
	SortedMap<Customer, String> sortedMap = new TreeMap<Customer, String>();
	Customer c1 = new Customer("[email protected]", "Employee 1");
	Customer c2 = new Customer("[email protected]", "Employee 1");
	sortedMap.put(c1, c1.getName());
	sortedMap.put(c2, c2.getName());
		
	System.out.println(sortedMap.size());   // Prints 1
    }
}

RELATED ARTICLES

Internal Implementation of ArrayList

ArrayList is an implementation of List interface, used to store a list of objects. Unlike normal arrays, it is a dynamic data structure, its size dynamically increases when its capacity is exhausted.

View Article

Understanding equals() and hashCode() methods

The equals() and hashCode() are two primary methods of Java's Object Class which work together to uniquely identify any object in Java.

View Article

Internal Implementation of HashMap

HashMap is popular data structure in Java which stores data in key-value format. This article describes the internal implementation to store and retrieve data in a hashmap.

View Article

Internal Implementation of HashSet

HashSet is a member of the Java Collection Framework which is used to store unique entries. This article describes how a HashSet is internally implemented to store unique entries.

View Article

Identity HashMap in Java

IdentityHashMap in Java is a special implentation of the Map interface designed to be used in special cases where reference equality is required.

View Article

Iterator and ListIterator in Java

The Java API provides the Iterator and ListIterator that are used to iterate over a Collection. This article covers the difference between the two and discuss how Emumeration is different from Iterat.

View Article

Introduction to Java Collections

The Java collections framework is a library that provides commonly reusable collection data structures. It consists of a set of various interfaces, implementations and algorithms used to represent...

View Article