TreeMap class is like HashMap. TreeMap stores key-value pairs. The main difference is that TreeMap sorts the key in ascending order. TreeMap is sorted as the ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
Pre-requisite:
Let’s go through pre-requisite that primarily includes constructors available in case of TreeMap before discussing further
- TreeMap() This default constructor constructs an empty TreeMap
- TreeMap(Map map) It creates a TreeMap with the entries from a map.
- TreeMap(Comparator compare) This is an argument constructor and it takes Comparator object to constructs an empty tree-based map. It will be sorted by using the Comparator compare.
- TreeMap(SortedMap sortedMap) It can be initialized as TreeMap with the entries from sortedMap.
Illustration:
Input : a = ["Alice", 1], b = ["Bob", 2]
Output : TreeMap = {"Alice" = 1, "Bob" = 2}
Input : a = [1, "First"], b = [2, "Second"], c = [3, "Third"]
Output : TreeMap = {1 = "First", 2 = "Second", 3 = "Third"}
Concept: Red-Black Trees
A red-black tree is a self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the colour (red or black). These colours are used to ensure that the tree remains balanced during insertions and deletions. Although the balance of the tree is not perfect, it is good enough to reduce the searching time and maintain it around O(log n) time, where n is the total number of elements in the tree. It must be noted that as each node requires only 1 bit of space to store the colour information, these types of trees show identical memory footprint to the classic (uncoloured) binary search tree.
- As the name of the algorithm suggests colour of every node in the tree is either black or red.
- The root node must be Black in colour.
- The red node can not have a red colour neighbours node.
- All paths from the root node to the null should consist of the same number of black nodes.
The above characteristics lead to certain properties of a node to possess which results out as follows:
- The left elements are always less than the parent element.
- Natural ordering is computed in logical comparison of the objects.
- The right elements are always greater than or equal to the parent element.
Syntax: Declaring an object of TreeMap or simply creating a TreeMap
Map<Key, Integer> treemap = new TreeMap<>();
Approach:
- Create a TreeMap.
- Create some entries to get entered in the TreeMap.
- Calculate hash code of Key {“key1”}. It will be generated as 118.
- Print the TreeMap using for loop traversal.
Implementation: Implementing red-black trees to showcase internal working of TreeMap
Example
Java
// Java Program to show Internal Working// of TreeMap in Java// Importing Map and TreeMap classes// from java.util packageimport java.util.Map;import java.util.TreeMap;// Standard Comparablepublic class Key implements Comparable<Key> { // Custom input final int data = 118; private String key; // Constructor of this class public Key(String key) { // Super keyword refers immediate parent class // object super(); // This keyword is a reference variable // referring to current object this.key = key; } // Print Key method public String printKey() { return this.key; } // Override compareTo method @Override public int compareTo(Key obj) { return key.compareTo(obj.key); }}// Main Classclass GFG { // Main driver method public static void main(String[] args) { // Initialize TreeMap // Declaring object of String type Map<Key, String> treemap = new TreeMap<>(); // Adding the elements in object of TreeMap // Custom inputs treemap.put(new Key("Key1"), "Alice"); treemap.put(new Key("Key4"), "Zeya"); treemap.put(new Key("Key3"), "Geek"); treemap.put(new Key("Key2"), "Bob"); // Iterate over object elements using for-each loop for (Map.Entry<Key, String> entry : treemap.entrySet()) // Print elements in TreeMap object System.out.println( "[" + entry.getKey().printKey() + " = " + entry.getValue() + "]"); }} |
Java
// Java Program to show Internal Working// of TreeMap in Java// Importing Map and TreeMap classes// from java.util packageimport java.util.Map;import java.util.TreeMap;// Standard Comparablepublic class Key implements Comparable<Key> { // Custom input final int data = 118; private String key; // Constructor of this class public Key(String key) { // Super keyword refers immediate parent class // object super(); // This keyword is a reference variable // referring to current object this.key = key; } // Print Key method public String printKey() { return this.key; } // Override compareTo method @Override public int compareTo(Key obj) { return key.compareTo(obj.key); }}// Main Classclass GFG { // Main driver method public static void main(String[] args) { // Initialize TreeMap // Declaring object of String type Map<Key, String> treemap = new TreeMap<>(); // Adding the elements in object of TreeMap // Custom inputs treemap.put(new Key("Key1"), "Alice"); treemap.put(new Key("Key4"), "Zeya"); treemap.put(new Key("Key3"), "Geek"); treemap.put(new Key("Key2"), "Bob"); // Iterate over object elements using for-each loop for (Map.Entry<Key, String> entry : treemap.entrySet()) // Print elements in TreeMap object System.out.println( "[" + entry.getKey().printKey() + " = " + entry.getValue() + "]"); }} |
Output explanation is pictorially represented in order to get the internal working of TreeMap nodes how the above output is generated for better understanding.
Note:
- Performance of TreeMap is slow in comparison with HashMap and LinkedHashMap.
- Tree implementation provides guaranteed log(n) time cost for the containsKey(), get(), put() and remove() operations.
