The inner workings of TreeMap in Java

TreeMap is a class of Java Collection Framework that implements NavigableMap Interface. It stores the elements of the map in a tree structure and provides an efficient alternative to store the key-value pairs in sorted order. Internally, TreeMap uses a red- black tree, which is a self-balancing binary search tree. A TreeMap must implement the Comparable Interface or a custom Comparator so that it can maintain the sorting order of its elements otherwise, we will encounter a java.lang.ClassCastException. This article aims to explain how TreeMap works internally in Java.

The inner workings of TreeMap in Java

To understand the inner workings of TreeMap, it is necessary to have an overview of the red-black tree algorithm, since TreeMap uses it to store elements.

Relation of Red Black Tree and TreeMap

The red-black tree is a self-balancing binary search tree, its properties are as follows:

• Each node contains an extra bit, represented by red or black. These colors are used to ensure the tree remains balanced.

• The color of root node is always black.

• A red node cannot have another node of the same color as its neighbor

• From the root node to the empty node, the number of black nodes on all paths must be the same

Now, let's see the structure of TreeMap:

If we add an element to the TreeMap, it will add the first entry in the first place. From the second element, it will check whether the key of current entry is greater or smaller than the previous entry. The keys with lower value will be added to the left and the ones with greater value will be added to the right of Parent entry.

Constructor of TreeMap

To use the TreeMap collection in our program, we first need to create an instance of the TreeMap class. For that Java provides the following constructors:

• TreeMap(): It will create an empty TreeMap collection

• TreeMap(Map mapInstance): We can create a tree map using entries from another map

• TreeMap(Comparator comparatorInstance): It allows us to create an empty tree map, sorted by using a comparator.

• TreeMap(SortedMap sortedmapInstance): We can also create a tree map with the entries from a sorted map.

Let's discuss a few examples to have a better understanding of the above discussed points.

Example

In the following example, we will create an empty TreeMap and then store some elements into it using the 'put()' method. We will print its details using for-each loop. Results will be displayed in sorted order.

import java.util.*;
public class Example1 {
   public static void main(String[] args) {
      // creating a TreeMap
      TreeMap<String, Integer> TrMap = new TreeMap<>();
      // Adding elements in the map
      TrMap.put("Kurti", 4000);
      TrMap.put("Shirt", 3000);
      TrMap.put("TShirt", 1500);
      TrMap.put("Watch", 2000);
      TrMap.put("Perfume", 2500);
      // printing the details of map 
      System.out.println("Elements of the map: ");
      // iterating through the map
      for (String unKey : TrMap.keySet()) {
         // printing details of each node
         System.out.println("Item: " + unKey + ", Price: " + 
TrMap.get(unKey));
      }
      String frstKey = TrMap.firstKey(); // accessing first key
      String lstKey = TrMap.lastKey(); // accessing last key
      System.out.println("Accessing name of first key in Map: " + 
frstKey);
      System.out.println("Accessing name of last key in Map: " + 
lstKey);
   }
}

Output

Elements of the map: 
Item: Kurti, Price: 4000
Item: Perfume, Price: 2500
Item: Shirt, Price: 3000
Item: TShirt, Price: 1500
Item: Watch, Price: 2000
Accessing name of first key in Map: Kurti
Accessing name of last key in Map: Watch

in conclusion

We started this article by defining a TreeMap and discussed its inner workings in the next section. TreeMap uses a red-black tree to store its elements, which is a self-balancing binary search tree. Additionally, we also discussed an example to illustrate how TreeMap works.

The above is the detailed content of The inner workings of TreeMap in Java. For more information, please follow other related articles on the PHP Chinese website!