TreeMap in Java

Features of TreeMap in Java

• TreeMap contains key-value mappings sorted in the natural ordering of their keys by default. The mappings can also be sorted using a comparator at map creation time.
• TreeMap implementation is not synchronised, i.e. if multiple threads access a Map concurrently where at least one thread makes structural modifications, it must be synchronised externally.
• TreeMap allows the use of null values but not null keys.
• Its implementation has a time cost of log(n) on all insertion, deletion and access operations.
• It does not support the Entry.setValue method. All entry pairs returned by methods in this class represent the mappings at the time they were produced.

Internal Working of Java TreeMap

1. Data Structure: Implemented as a Red-Black Tree (self-balancing binary search tree).
2. Key-Value Pairs: Stores data in key-value pairs, where keys are unique.
3. Ordering: Keys are sorted in their natural order or by a custom comparator.
4. NavigableMap Interface: Implements NavigableMap, allowing operations like ceiling(), floor(), etc.
5. Complexity: Most operations like put(), remove(), get() have O(log n) time complexity.
6. Red-Black Tree Properties: Ensures balanced tree structure for efficient search, insertion, and deletion.

Constructors TreeMap in Java

1. TreeMap()

It constructs a new, empty treemap with the natural ordering of its keys.

TreeMap<Integer, String> tree_map = new TreeMap<Integer, String>();

2. TreeMap(Comparator<? super K> comparator)

It constructs a new, empty treemap, whose keys are ordered according to the given comparator.

import java.util.*;
import java.util.concurrent.*;
// Comparator implementation
class Sort_keys implements Comparator<K> 
{
     // Comparator code
}
// Main class
public class Main 
{
    public static void main(String[] args)
    {
       TreeMap<K, V> tree_map = new TreeMap<K, V>(new Sort_keys());
     }
}

3. TreeMap(Map<? extends K,? extends V> m)

It constructs a new tree map containing the same mappings as the given map, with the natural ordering of its keys.

import java.util.*;
public class Main 
{
public static void main(String[] args)
   {
      Map<Integer, String> hash_map  = new HashMap<Integer, String>();

      // code to perform operations on hash_map

      TreeMap<Integer, String> tree_map = new TreeMap<Integer, String>(hash_map);
    }
}

4. TreeMap(SortedMap<K,? extends V> m)

It constructs a new tree map containing the same mappings and ordering as the specified sorted map.

import java.util.*;
import java.util.concurrent.*;
public class Main 
{
public static void main(String[] args)
   {
     SortedMap<Integer, String> sorted_map  = new ConcurrentSkipListMap<Integer, String>();


     // code to perform operations on sorted_map


     TreeMap<Integer, String> tree_map = new TreeMap<Integer, String>(sorted_map);
   }
}

Methods of Java TreeMap Class

Also see,  Swap Function in Java

Basic Operations on TreeMap

• Adding elements using put() and putAll() functions.
• Removing elements using remove() function.
• Accessing elements using entrySet(), values(), keySet() and get() functions.
• Replacing elements using replace() and replaceAll() functions.

• Java

Java

import java.util.TreeMap;

public class Main
 {
  public static void main(String[] args) 
     {
      TreeMap<String, String> India = new TreeMap<>();

      // Adding or insertion
      India.put("India","New Delhi");

      TreeMap<String, String> country = new TreeMap<>();
      country.putAll(India);

      country.put("Australia","Canberra");
      country.put("Germany","Berlin");
      country.put("France", "London");

        // Accessing elements
      System.out.println("TreeMap of country-capital: " + country.entrySet());
      System.out.println("\nList of keys (Country): " + country.keySet());
      System.out.println("List of values (Capitals): " + country.values());
      System.out.println("\nThe capital of France is :" + country.get("France"));
      System.out.println();

      // Replacing elements
      country.replace("France","Paris");
      System.out.println("Correcting the capital the of France to " + country.replace("France","Paris"));
      System.out.println(country);
      System.out.println("\nAbbreviating the names of all capitals.");
      country.replaceAll((key , oldValue) -> oldValue.substring(0, 3));
      System.out.println(country + "\n");

      //Removing elements
      System.out.println("Removing Australia: " + country.remove("Australia"));
      System.out.println(country);
  }
}

You can also try this code with Online Java Compiler

Run Code

Output:

TreeMap of country-capital: [Australia=Canberra, France=London, Germany=Berlin, India=New Delhi]

List of keys Country): [Australia, France, Germany, India]
List of values (Capitals): [Canberra, London, Berlin, New Delhi]

The capital of France is :London

Correcting the capital the of France to Paris
{Australia=Canberra, France=Paris, Germany=Berlin, India=New Delhi}

Abbreviating the names of all capitals.
{Australia=Can, France=Par, Germany=Ber, India=New}

Removing Australia: Can
{France=Par, Germany=Ber, India=New}

Navigation Operations on TreeMap

• Obtain first and last mappings or keys.
• Obtain highest and lowest mappings or keys.
• Use of ceiling and floor methods.
• Use of pollFirstEntry() and pollLastEntry() methods.    

• Java

Java

import java.util.TreeMap;

public class Main 
{
  public static void main(String[] args) 
     {      
      TreeMap<String, String> country = new TreeMap<>();

      country.put("India","New Delhi");
      country.put("Australia","Canberra");
      country.put("Germany","Berlin");
      country.put("France", "Paris");
      country.put("Japan", "Tokyo");
      country.put("Russia", "Moscow");
      country.put("Brazil", "Brasilia");

      System.out.println("TreeMap contents: " + country);

      // First and last
      System.out.println("First key: " + country.firstKey());
      System.out.println("First entry " + country.firstEntry());
      System.out.println("Last key " + country.lastKey());
      System.out.println("Last entry :" + country.lastEntry());
      System.out.println();

      // Highest and lowest
      System.out.println("Higher key: " + country.higherKey("Japan"));
      System.out.println("Higher entry: " + country.higherEntry("Japan"));
      System.out.println("Lower key: " + country.lowerKey("Japan"));
      System.out.println("Lower entry: " + country.lowerEntry("Japan"));
      System.out.println();

      //Ceiling and floor
      System.out.println("Ceiling key: " + country.ceilingKey("Japan"));
      System.out.println("Ceiling entry: " + country.ceilingEntry("Japan"));
      System.out.println("Floor key: " + country.floorKey("Japan"));
      System.out.println("Floor entry: " + country.floorEntry("Japan"));
      System.out.println();

      // poll first and last entry
      System.out.println("Poll first entry: " + country.pollFirstEntry());
      System.out.println("Poll last entry: " + country.pollLastEntry());
      System.out.println(country);
      System.out.println();
    }
}

You can also try this code with Online Java Compiler

Run Code

Output:

TreeMap contents: {Australia=Canberra, Brazil=Brasilia, France=Paris, Germany=Berlin, India=New Delhi, Japan=Tokyo, Russia=Moscow}
First key: Australia
First entry Australia=Canberra
Last key Russia
Last entry :Russia=Moscow

Higher key: Russia
Higher entry: Russia=Moscow
Lower key: India
Lower entry: India=New Delhi

Ceiling key: Japan
Ceiling entry: Japan=Tokyo
Floor key: Japan
Floor entry: Japan=Tokyo

Poll first entry: Australia=Canberra
Poll last entry: Russia=Moscow
{Brazil=Brasilia, France=Paris, Germany=Berlin, India=New Delhi, Japan=Tokyo}

• Use of headMap(), tailMap() and subMap() functions.

• Java

Java

import java.util.TreeMap;

public class Main 
{
  public static void main(String[] args) 
  {      
      TreeMap<String, String> country = new TreeMap<>();

      country.put("India","New Delhi");
      country.put("Australia","Canberra");
      country.put("Germany","Berlin");
      country.put("France", "Paris");
      country.put("Japan", "Tokyo");
      country.put("Russia", "Moscow");
      country.put("Brazil", "Brasilia");

      System.out.println("TreeMap contents: " + country);

      // First and last
      System.out.println("\nHeadMap: " + country.headMap("Germany"));
      System.out.println("\nTailMap: " + country.tailMap("Germany"));
      System.out.println("\nSubMap: " + country.subMap("Germany","Japan"));
    }
}

You can also try this code with Online Java Compiler

Run Code

Output:

TreeMap contents: {Australia=Canberra, Brazil=Brasilia, France=Paris, Germany=Berlin, India=New Delhi, Japan=Tokyo, Russia=Moscow}

HeadMap: {Australia=Canberra, Brazil=Brasilia, France=Paris}

TailMap: {Germany=Berlin, India=New Delhi, Japan=Tokyo, Russia=Moscow}

SubMap: {Germany=Berlin, India=New Delhi}

Advantages of TreeMap in Java

1. Sorted Order: Automatically maintains keys in natural or custom order, making it ideal for applications requiring sorted data.
2. Efficient Search: Red-Black Tree structure offers O(log n) time complexity for get(), put(), and remove().
3. NavigableMap Interface: Implements the NavigableMap interface, supporting efficient navigation methods like ceiling(), floor(), higher(), and lower().
4. No Duplicates: Ensures uniqueness of keys, providing a reliable map structure where duplicate keys are not allowed.
5. Range Views: Allows operations like subMap(), headMap(), and tailMap() for efficient range querying.
6. Thread Safety: While not synchronized, individual operations on TreeMap are thread-safe when accessed by a single thread.
7. Flexible Sorting: Can use a custom comparator for sorting keys, offering flexibility for complex ordering.

Disadvantages of TreeMap in Java

1. Slower than HashMap: Due to sorting and balancing, TreeMap operations (like put() and get()) are slower (O(log n)) compared to HashMap (O(1) average).
2. No Null Keys: TreeMap does not allow null keys, unlike HashMap, which can store null values.
3. Memory Overhead: The Red-Black Tree structure requires extra memory for tree nodes and balancing information.
4. Not Synchronized: By default, TreeMap is not thread-safe for concurrent modifications. External synchronization is needed in multi-threaded environments.
5. Comparator Dependency: If the comparator is not provided, the natural ordering of keys must be consistent, which might not always be desirable.
6. Performance with Large Data: Performance may degrade with very large datasets, as balancing the tree requires more time compared to other structures.

Frequently Asked Questions

What is the SortedMap interface, and how is it different from TreeMap?

The SortedMap interface provides a natural ordering of its keys for easy traversal. Its parent interface is the Map interface, and its subinterface is the NavigableMap.

SortedMap cannot be used to create objects as it is an interface. The implementation of the sortedMap is the TreeMap using which objects can be created. While the SortedMap restricts the use of null keys and null values, the TreeMap imposes restrictions only on the use of null keys.

Is TreeMap ordered in Java?

Yes, TreeMap is ordered. It stores keys in their natural order or according to a custom comparator provided at the time of creation.

Does TreeMap allow null keys?

No, TreeMap does not allow null keys. It throws a NullPointerException if you attempt to insert a null key.

What is the difference between TreeMap and TreeSet in Java?

TreeMap stores key-value pairs, while TreeSet stores only unique keys. Both use a Red-Black Tree, but TreeMap maps keys to values, whereas TreeSet only maintains unique keys.

Can TreeMap have duplicate values?

Yes, TreeMap allows duplicate values but not duplicate keys. The values can be repeated, but each key must be unique.

Conclusion

TreeMaps are special and extremely useful. The mappings they store can be arranged in the ascending order of its keys or by using the comparator as discussed. Since the mappings are already sorted, they quickly access its key-value pairs. This blog explains the TreeMap class in detail, along with its features and constructors. It also lists out the various functions and methods provided by this class to work with key-value mappings. 

Check out this problem - Reverse Nodes In K Group

Recommended Articles:

• Swap Function in Java