2.4.2 TreeMap Explained

The TreeMap class in Java is a part of the Java Collections Framework and implements the NavigableMap interface. It is used to store key-value pairs in a sorted order based on the natural ordering of the keys or by a specified comparator. Understanding TreeMap is crucial for managing sorted maps efficiently in Java SE 11 applications.

Key Concepts

1. Sorted Order

A TreeMap stores its elements in a sorted order based on the keys. The sorting can be based on the natural ordering of the keys or by a specified comparator. This ensures that the keys are always in a sorted sequence, making it easy to retrieve elements in a specific order.

Example

        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(3, "Cherry");
        treeMap.put(1, "Apple");
        treeMap.put(2, "Banana");
        System.out.println(treeMap); // Output: {1=Apple, 2=Banana, 3=Cherry}
    

2. Red-Black Tree Structure

Internally, TreeMap uses a Red-Black tree, which is a self-balancing binary search tree. This structure ensures that the tree remains balanced, providing logarithmic time complexity for basic operations like insertion, deletion, and search.

Example

        TreeMap<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("Dog", 1);
        treeMap.put("Cat", 2);
        treeMap.put("Bird", 3);
        System.out.println(treeMap); // Output: {Bird=3, Cat=2, Dog=1}
    

3. NavigableMap Interface

The TreeMap class implements the NavigableMap interface, which extends the SortedMap interface. This provides additional methods for navigation, such as finding the greatest key less than or equal to a given key, or the smallest key greater than or equal to a given key.

Example

        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(1, "Apple");
        treeMap.put(2, "Banana");
        treeMap.put(3, "Cherry");
        System.out.println(treeMap.floorEntry(2)); // Output: 2=Banana
        System.out.println(treeMap.ceilingEntry(2)); // Output: 2=Banana
    

4. Performance

A TreeMap provides logarithmic time complexity for basic operations like put, get, and remove. This makes it efficient for large datasets, especially when you need to maintain a sorted order of keys.

Example

        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(1, "Apple");
        treeMap.put(2, "Banana");
        treeMap.put(3, "Cherry");
        System.out.println(treeMap.get(2)); // Output: Banana
    

Examples and Analogies

Think of a TreeMap as a dictionary where words (keys) are arranged in alphabetical order. When you look up a word, you can easily find it because it is sorted. The dictionary also allows you to find the word that comes before or after a given word, similar to the navigation methods provided by TreeMap.

By mastering TreeMap, you can efficiently manage sorted maps in your Java SE 11 applications, ensuring that your data is always organized and accessible in a specific order.