TreeMap

In Java’s collection framework, the Map interface is the foundation for any key‑value store. Among the various implementations, TreeMap stands out because it keeps its entries sorted by key. Unlike the hash‑based HashMap, which offers constant‑time lookups on average, TreeMap relies on a self‑balancing binary search tree—specifically, a Red‑Black Tree—to guarantee order and provide logarithmic‑time operations.

How TreeMap Works

Red‑Black Tree Basics

A Red‑Black Tree is a type of binary search tree that enforces balance through a set of color‑based rules:

• Node colors: Each node is either red or black.
• Root and leaves: The root is always black, and all leaves (null children) are considered black.
• Red property: No two consecutive red nodes appear on any path.
• Black depth: Every path from a node to its descendant leaves contains the same number of black nodes.

These constraints keep the tree height bounded by (2\log_2(n+1)), ensuring that operations such as insertion, deletion, and lookup run in O(log n) time.

Ordering Guarantees

When a key is inserted, the tree places it according to its natural ordering (e.g., Comparable implementation) or a custom Comparator supplied at construction. Because the left child is always less than the parent and the right child is always greater, an in‑order traversal yields the keys in ascending order. This property is what makes TreeMap a sorted map.

Null Keys and Values

TreeMap permits null values but rejects null keys. A null key cannot be compared, which would violate the ordering rules and could lead to a NullPointerException. In contrast, HashMap accepts a single null key and any number of null values.

Performance Profile

While TreeMap is slower in typical scenarios, its predictable logarithmic bounds make it attractive for workloads where worst‑case performance matters.

API Highlights

Beyond the standard Map methods, TreeMap offers navigation utilities that exploit its sorted nature:

• firstKey(), lastKey() – retrieve the smallest or largest key.
• lowerKey(K key), floorKey(K key), ceilingKey(K key), higherKey(K key) – find neighboring keys.
• subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) – obtain a view of a key range.
• headMap(K toKey, boolean inclusive), tailMap(K fromKey, boolean inclusive) – views before or after a key.

These methods enable efficient range queries and ordered traversals without extra sorting steps.

Sample Code

import java.util.Map;
import java.util.TreeMap;

public class TreeMapDemo {
    public static void main(String[] args) {
        // Create a TreeMap that sorts keys alphabetically
        TreeMap<String, Integer> scores = new TreeMap<>();

        // Populate the map
        scores.put("Alice", 85);
        scores.put("Bob", 92);
        scores.put("Charlie", 78);
        scores.put("David", 90);

        // 1. Iterate – keys appear in sorted order
        System.out.println("--- Sorted iteration ---");
        for (Map.Entry<String, Integer> entry : scores.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // 2. Navigation examples
        System.out.println("\nFirst key (smallest): " + scores.firstKey());
        System.out.println("Last key (largest): " + scores.lastKey());
        System.out.println("Key just before 'Charlie': " + scores.lowerKey("Charlie"));

        // 3. Submap – keys from Alice to David inclusive
        System.out.println("\nSubmap (Alice to David):");
        scores.subMap("Alice", true, "David", true)
              .forEach((k, v) -> System.out.println(k + ": " + v));
    }
}

Running this program prints the entries in alphabetical order and demonstrates the navigation methods.

When to Choose TreeMap

Conversely, if you only need fast lookups and insertion without ordering, HashMap or LinkedHashMap may be preferable.

Summary

TreeMap is a powerful tool in Java’s arsenal for any situation that demands an ordered key‑value store. Its underlying Red‑Black Tree guarantees that operations stay within logarithmic time while preserving a strict key order. By leveraging its navigation methods, developers can perform efficient range queries and maintain sorted data without resorting to additional sorting logic. Understanding when the trade‑offs of TreeMap are worth it—especially compared to hash‑based maps—enables more robust and performant application design.