Before we jump into TreeMap, let us first look into Tree Data Structure.
The basic building block for the tree is the node. Tree is nothing but hierarchial ordering of nodes. Some of the basic definitions are defined below:
Root:The top node in a tree. In the above tree structure “A” is the root.
Parent:The node which is predecessor of any node.In other words the node which has child node(s).In the above tree structure “D” is the parent for “E”,”F” and “G”.
Child:The node which is descendant of any node. In a tree, all the nodes except root are child nodes.In the above tree structure “E”,”F” and “G” are the children of “D”.
Siblings:A group of nodes with the same parent.In the above tree structure “E”,”F” and “G” are the siblings.
Leaf:A node with no children.In the above tree structure “C”,”E”,”F”, “G”,”H” and “I” are the leaf nodes.
Now let us know what is a Binary Tree?
The above is an example of binary tree.Binary tree is a special tree where each node can have no more than two children.
Now let us know what is a Binary Search Tree(BST)?
The above is an example of Binary Search Tree. In this case, a node’s left child must have a value less than its parent’s value and the node’s right child must have a value greater than or equal to its parent value.
Balanced Binary Search Tree(Balanced BST)
Balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically.
Advantages of Balanced BST:
Most operations on a BST take time proportional to the height of the tree, so it is desirable to keep the height small. For normal BST, the worst case for search, add and remove operations is O(n), whereas in case of Binary BST it is O(log n).
Self-balancing binary trees solve this problem by performing transformations on the tree at key times, in order to reduce the height. Although a certain overhead is involved, it is justified in the long run by ensuring fast execution of later operations.
Implementations of Balanced BST
Following are popular Balanced Binary Search tree implementations.
- 2-3 tree
- AA tree
- AVL tree
- Red-black tree
- Scapegoat tree
- Splay tree
- Treap
Now let us come to our main topic i.e., TreeMap.TreeMap is a Red-Black tree based implementation of Map.
Following are the properties of Red-black tree.
- Every node is either red or black.
- Every leaf is a NIL node, and is colored black.
- If a node is red, then both its children are black. That is a red node can’t have a red child node.
- Every simple path from a node to a descendant leaf contains the same number of black nodes.
- The root node is always black
We will not go in deep into Red-Black Tree as it is based on some complex algorithms and in any case these internal details are not needed for us.
In TreeMap the entries(key-value pairs) are sorted based on the keys.
The objects to be used as key in the TreeMap should implement Comparable interface.Otherwise a Comparator which can compare the keys needs to be passed an argument while creating the TreeMap.
Example
Let us take the example of Employee. In this case, the natural ordering of the Employee is by Id. We have also created two Comparators SalaryComparator and NameComparator to sort Employees by Salary and Name respectively.
Employee Class which implements Comparable
package com.comparable.example;
public class Employee implements Comparable{
private String name;
private Long salary;
private Long id;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Long getSalary() {
return salary;
}
public Employee(String name, Long salary, Long id) {
this.name = name;
this.salary = salary;
this.id = id;
}
@Override
public String toString() {
return “Employee [name=” + name + “, salary=” + salary + “, id=” + id
+ “]”;
}
public void setSalary(Long salary) {
this.salary = salary;
}
public Long getId() {
return id;
}
public void setId(Long id) {
this.id = id;
}
@Override
public int compareTo(Employee employee) {
return this.getId().compareTo(employee.getId());
}
}
SalaryComparator
package com.comparator.example;
import java.util.Comparator;
import com.comparable.example.Employee;
public class SalaryComparator implements Comparator{
@Override
public int compare(Employee emp1, Employee emp2) {
return emp1.getSalary().compareTo(emp2.getSalary());
}
}
NameComparator
package com.comparator.example;
import java.util.Comparator;
import com.comparable.example.Employee;
public class NameComparator implements Comparator{
@Override
public int compare(Employee emp1, Employee emp2) {
return emp1.getName().compareTo(emp2.getName());
}
}
TestEmployee class
package com.comparable.example;
import java.util.Map;
import java.util.TreeMap;
import com.comparator.example.NameComparator;
import com.comparator.example.SalaryComparator;
public class TestEmployee {
public static void main(String[] args) {
Map<Employee,String> treeMap = new TreeMap<Employee,String>();
Map<Employee,String> salaryBasedTreeMap = new TreeMap<Employee,String>(new SalaryComparator());
Map<Employee,String> nameBasedTreeMap = new TreeMap<Employee,String>(new NameComparator());
Employee emp1 = new Employee(“Gyan”, 1000000L, 1L);
treeMap.put(emp1, “Bhubaneswar”);
salaryBasedTreeMap.put(emp1, “Bhubaneswar”);
nameBasedTreeMap.put(emp1, “Bhubaneswar”);
Employee emp2 = new Employee(“Praveen”, 1500000L, 2L);
treeMap.put(emp2, “New Delhi”);
salaryBasedTreeMap.put(emp2, “New Delhi”);
nameBasedTreeMap.put(emp2, “New Delhi”);
Employee emp3 = new Employee(“Rochit”, 800000L, 4L);
treeMap.put(emp3, “Bangalore”);
salaryBasedTreeMap.put(emp3, “Bangalore”);
nameBasedTreeMap.put(emp3, “Bangalore”);
Employee emp4 = new Employee(“Vivek”, 12000000L, 3L);
treeMap.put(emp4, “Calcutta”);
salaryBasedTreeMap.put(emp4, “Calcutta”);
nameBasedTreeMap.put(emp4, “Calcutta”);
Employee emp5 = new Employee(“Prabhakar”, 1800000L, 5L);
treeMap.put(emp5, “Mangalore”);
salaryBasedTreeMap.put(emp5, “Mangalore”);
nameBasedTreeMap.put(emp5, “Mangalore”);
Employee emp6 = new Employee(“Sudeep”, 1600000L, 6L);
treeMap.put(emp6, “Chennai”);
salaryBasedTreeMap.put(emp6, “Chennai”);
nameBasedTreeMap.put(emp6, “Chennai”);
System.out.println(“Natural Ordering by Id:”+treeMap);
System.out.println(“Ordering by Salary:”+salaryBasedTreeMap);
System.out.println(“Ordering by Name:”+nameBasedTreeMap);
}
}
Output
Natural Ordering by Id:{Employee [name=Gyan, salary=1000000, id=1]=Bhubaneswar, Employee [name=Praveen, salary=1500000, id=2]=New Delhi, Employee [name=Vivek, salary=12000000, id=3]=Calcutta, Employee [name=Rochit, salary=800000, id=4]=Bangalore, Employee [name=Prabhakar, salary=1800000, id=5]=Mangalore, Employee [name=Sudeep, salary=1600000, id=6]=Chennai}
Ordering by Salary:{Employee [name=Rochit, salary=800000, id=4]=Bangalore, Employee [name=Gyan, salary=1000000, id=1]=Bhubaneswar, Employee [name=Praveen, salary=1500000, id=2]=New Delhi, Employee [name=Sudeep, salary=1600000, id=6]=Chennai, Employee [name=Prabhakar, salary=1800000, id=5]=Mangalore, Employee [name=Vivek, salary=12000000, id=3]=Calcutta}
Ordering by Name:{Employee [name=Gyan, salary=1000000, id=1]=Bhubaneswar, Employee [name=Prabhakar, salary=1800000, id=5]=Mangalore, Employee [name=Praveen, salary=1500000, id=2]=New Delhi, Employee [name=Rochit, salary=800000, id=4]=Bangalore, Employee [name=Sudeep, salary=1600000, id=6]=Chennai, Employee [name=Vivek, salary=12000000, id=3]=Calcutta}