Java TreeMap

---

The TreeMap class in Java is part of the java.util package and implements the NavigableMap interface. It stores key-value pairs in a sorted order based on the keys. The TreeMap is backed by a Red-Black Tree, ensuring that the map remains balanced and offers O(log n) time complexity for most operations. This makes TreeMap an ideal choice when you need a map that maintains order and provides efficient retrieval, insertion, and deletion operations.

In this article, we’ll dive deep into the TreeMap class, its core features, methods, and provide practical examples of its use in Java.

---

What is TreeMap in Java?

A TreeMap is a NavigableMap that stores keys in their natural order or according to a custom Comparator provided at map creation time. It implements Map and extends SortedMap. The TreeMap is similar to a HashMap but with one major difference: the keys in a TreeMap are ordered.

The primary features of TreeMap include:

• Sorted Keys: The keys are ordered according to their natural ordering or by a specified comparator.
• Navigable Operations: Provides methods like higherKey(), lowerKey(), and subMap() to navigate and manipulate sorted keys efficiently.
• Balanced Tree: TreeMap is backed by a Red-Black tree, ensuring that the map stays balanced for efficient searching and updates.
• No Null Keys: TreeMap does not allow null keys but allows null values.

---

Core Features and Methods of TreeMap

Here are some of the key methods and features of TreeMap:

1. Constructor

TreeMap<K, V>()
TreeMap(Comparator<? super K> comparator)

• The first constructor creates a TreeMap with keys sorted according to their natural ordering.
• The second constructor creates a TreeMap with keys sorted by a custom comparator.

2. Basic Methods

• put(K key, V value): Adds a key-value pair to the map.

  map.put("Apple", 3);
  

• get(Object key): Retrieves the value associated with the specified key.

  Integer value = map.get("Apple");
  

• remove(Object key): Removes the key-value pair for the given key.

  map.remove("Apple");
  

• containsKey(Object key): Checks if a key exists in the map.

  boolean exists = map.containsKey("Apple");
  

3. Navigable Methods

• higherKey(K key): Returns the first key that is strictly greater than the specified key.

  K higherKey(K key);
  

• lowerKey(K key): Returns the last key that is strictly less than the specified key.

  K lowerKey(K key);
  

• ceilingKey(K key): Returns the least key that is greater than or equal to the specified key.

  K ceilingKey(K key);
  

• floorKey(K key): Returns the greatest key that is less than or equal to the specified key.

  K floorKey(K key);
  

• subMap(K fromKey, K toKey): Returns a view of the portion of the map whose keys range from fromKey (inclusive) to toKey (exclusive).

  SortedMap<K, V> subMap(K fromKey, K toKey);
  

4. Poll Methods

• pollFirstEntry(): Retrieves and removes the first (lowest) entry.

  Map.Entry<K, V> pollFirstEntry();
  

• pollLastEntry(): Retrieves and removes the last (highest) entry.

  Map.Entry<K, V> pollLastEntry();
  

5. Other Useful Methods

• descendingMap(): Returns a view of the map with entries in descending order.

  NavigableMap<K, V> descendingMap();
  

• size(): Returns the number of key-value pairs in the map.

  int size = map.size();
  

---

Example: Basic Usage of TreeMap

Here’s a simple example of how to use TreeMap in Java:

import java.util.*;

public class TreeMapExample {
    public static void main(String[] args) {
        // Create a TreeMap with String keys and Integer values
        TreeMap<String, Integer> map = new TreeMap<>();

        // Add key-value pairs
        map.put("Apple", 3);
        map.put("Banana", 2);
        map.put("Mango", 1);
        map.put("Pineapple", 4);

        // Display the entire TreeMap (keys are sorted)
        System.out.println("TreeMap: " + map);

        // Retrieve a value based on key
        System.out.println("Value for 'Apple': " + map.get("Apple"));

        // Remove an entry
        map.remove("Banana");
        System.out.println("TreeMap after removing 'Banana': " + map);

        // Check if a key exists
        System.out.println("Contains 'Mango'? " + map.containsKey("Mango"));

        // Get the first and last keys
        System.out.println("First Key: " + map.firstKey());
        System.out.println("Last Key: " + map.lastKey());
    }
}

Output:

TreeMap: {Apple=3, Banana=2, Mango=1, Pineapple=4}
Value for 'Apple': 3
TreeMap after removing 'Banana': {Apple=3, Mango=1, Pineapple=4}
Contains 'Mango'? true
First Key: Apple
Last Key: Pineapple

Explanation:

• The TreeMap stores the entries in sorted order by default (alphabetical order for String keys).
• get() retrieves the value associated with a key.
• remove() deletes a key-value pair from the map.
• containsKey() checks whether a key exists in the map.
• firstKey() and lastKey() retrieve the first and last keys in the sorted map.

---

Example: Using TreeMap with a Custom Comparator

You can also create a TreeMap that sorts keys based on a custom Comparator. Here’s an example that sorts String keys in reverse order:

import java.util.*;

public class TreeMapWithComparator {
    public static void main(String[] args) {
        // Create a TreeMap with a custom comparator (reverse order of strings)
        TreeMap<String, Integer> map = new TreeMap<>(Collections.reverseOrder());

        // Add key-value pairs
        map.put("Apple", 3);
        map.put("Banana", 2);
        map.put("Mango", 1);
        map.put("Pineapple", 4);

        // Display the TreeMap (keys are sorted in reverse order)
        System.out.println("TreeMap with Reverse Order: " + map);
    }
}

Output:

TreeMap with Reverse Order: {Pineapple=4, Mango=1, Banana=2, Apple=3}

Explanation:

• The TreeMap is created with a Comparator that sorts the keys in reverse order.
• The map’s keys are displayed in descending order (i.e., the highest key first).

---

When to Use TreeMap

TreeMap is an excellent choice when you need:

1. Sorted Map: To maintain keys in sorted order based on their natural ordering or a custom comparator.
2. Efficient Navigation: To perform range queries, navigate through the keys, and retrieve the closest matches.
3. Ordered Data: When you need the map entries to be automatically sorted.

---

TreeMap vs HashMap

Here’s a quick comparison between TreeMap and HashMap:

Feature	TreeMap	HashMap
Ordering	Sorted by natural ordering or comparator.	No guaranteed order.
Performance	O(log n) for most operations due to Red-Black tree.	O(1) for most operations on average.
Null Keys	Does not allow null keys.	Allows null keys.
Navigation	Provides navigation methods (e.g., higherKey(), floorKey()).	No navigation methods.

---

---