The TreeMap class is a part of the Java Collections Framework and provides a map implementation that stores key-value pairs in a sorted order. It implements the NavigableMap and SortedMap interfaces, which means that the keys in a TreeMap are maintained either in their natural order (if the keys implement the Comparable interface) or in an order determined by a custom comparator provided at the time of creation.

TreeMap is particularly useful when you need to perform range queries or iterate over keys in a sorted manner. However, note that TreeMap does not allow null keys (although null values are permitted) and its operations typically have logarithmic time complexity due to the underlying red-black tree data structure.

Key Characteristics of TreeMap

• Sorted Order: Automatically sorts keys in natural order or according to a custom comparator.
• Navigable Methods: Provides methods like firstKey(), lastKey(), ceilingKey(), and floorKey() for navigating the sorted keys.
• Underlying Structure: Implemented using a red-black tree, ensuring efficient (O(log n)) performance for insertion, removal, and lookup operations.
• No Null Keys: Unlike some other map implementations, TreeMap does not permit null keys.
• Dynamic Size: Automatically grows or shrinks as key-value pairs are added or removed.

Syntax for Creating a TreeMap

Basic Syntax Using Natural Order:

TreeMap<KeyType, ValueType> treeMap = new TreeMap<KeyType, ValueType>();

• Explanation:
  • This creates a new TreeMap that will store keys of type KeyType and values of type ValueType, sorting the keys by their natural order.

Syntax with a Custom Comparator:

TreeMap<KeyType, ValueType> treeMap = new TreeMap<KeyType, ValueType>(customComparator);

• Explanation:
  • Here, customComparator is an instance of a class that implements Comparator<KeyType>.
  • The TreeMap will use this comparator to sort the keys in the desired order.

Examples

Example 1: Basic TreeMap Operations Using Natural Order

In this example, we create a TreeMap of String keys and Integer values. We add several key-value pairs, and then we display the map. The keys will be automatically sorted in their natural (alphabetical) order.

Example Explanation:

• TreeMap Creation:
  • A TreeMap<String, Integer> named studentGrades is created.
• Inserting Elements:
  • The put() method adds entries, such as ("Charlie", 78), ("Alice", 88), ("David", 92), and ("Bob", 90).
• Automatic Sorting:
  • The keys are automatically sorted in alphabetical order: "Alice", "Bob", "Charlie", "David".
• Outcome:
  • The printed TreeMap shows the key-value pairs in the sorted order based on the keys.

Example 2: TreeMap with Custom Comparator

This example demonstrates how to use a custom comparator to sort keys in descending order. We create a TreeMap of Integer keys and String values. The custom comparator will reverse the natural ordering, so the largest key appears first.

Example Explanation:

• Custom Comparator Definition:
  • A DescendingComparator class implements Comparator<Integer> and overrides compare() to sort integers in descending order.
• TreeMap Creation with Comparator:
  • The TreeMap scoreBoard is instantiated with the custom comparator, ensuring that keys (scores) are sorted in descending order.
• Inserting Elements:
  • The put() method adds entries such as (50, "Player A"), (75, "Player B"), (60, "Player C"), and (85, "Player D").
• Outcome:
  • The printed TreeMap displays the scores in descending order: 85, 75, 60, 50.

Understanding TreeMap is crucial for applications that require sorted data, efficient range queries, and navigation through key-value pairs in a defined order.