TreeMap basics

The TreeMap class in Java is part of the java.util package and implements the NavigableMap interface, which is a subtype of the SortedMap interface. It provides a map that is sorted according to the natural ordering of its keys or by a comparator provided at map creation time. TreeMap is backed by a Red-Black tree, which guarantees that the map will be in sorted order and that the basic operations (such as get, put, remove) will have logarithmic time complexity.

Key Features of TreeMap

1. Sorted Order: The keys in a TreeMap are sorted according to their natural ordering or by a specified comparator.
2. Navigable Operations: TreeMap provides methods to navigate through the map, such as lowerKey, floorKey, ceilingKey, and higherKey.
3. Submap Views: TreeMap offers efficient means to get submaps, head maps, and tail maps.
4. Logarithmic Time Performance: The basic operations (get, put, remove) have logarithmic time complexity, O(log n).
5. Null Values: TreeMap allows null values, but not null keys.

Creating a TreeMap

Here’s how to create a TreeMap in Java:

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

public class TreeMapExample {
    public static void main(String[] args) {
        Map<String, Integer> treeMap = new TreeMap<>();
    }
}

Basic Operations

Adding Key-Value Pairs

To add key-value pairs to a TreeMap, you can use the put method:

treeMap.put("Apple", 1);
treeMap.put("Banana", 2);
treeMap.put("Orange", 3);

Removing Key-Value Pairs

To remove key-value pairs from a TreeMap, you can use the remove method:

treeMap.remove("Banana");

Retrieving Values

To retrieve values from a TreeMap, you can use the get method:

int value = treeMap.get("Apple");  // returns 1

Checking for Keys or Values

To check if a TreeMap contains a specific key or value, you can use the containsKey and containsValue methods:

boolean hasApple = treeMap.containsKey("Apple");  // returns true
boolean hasValue2 = treeMap.containsValue(2);  // returns false

Iterating Over Entries

To iterate over the entries in a TreeMap, you can use an iterator, enhanced for loop, or forEach method:

// Using entrySet() and enhanced for loop
for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// Using forEach method (Java 8 and later)
treeMap.forEach((key, value) -> System.out.println(key + ": " + value));

Example Program

Here’s a complete example demonstrating various operations with TreeMap:

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

public class TreeMapExample {
    public static void main(String[] args) {
        Map<String, Integer> treeMap = new TreeMap<>();

        // Adding key-value pairs
        treeMap.put("Apple", 1);
        treeMap.put("Banana", 2);
        treeMap.put("Orange", 3);
        treeMap.put("Apple", 4);  // Duplicate key, value will be replaced

        // Checking size
        System.out.println("Size of treeMap: " + treeMap.size());  // Output: 3

        // Removing a key-value pair
        treeMap.remove("Banana");

        // Retrieving a value
        System.out.println("Value for key 'Apple': " + treeMap.get("Apple"));  // Output: 4

        // Checking if key or value exists
        System.out.println("Contains key 'Apple': " + treeMap.containsKey("Apple"));  // Output: true
        System.out.println("Contains value 2: " + treeMap.containsValue(2));  // Output: false

        // Iterating over entries
        System.out.println("Entries in treeMap:");
        for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // Using forEach method (Java 8 and later)
        treeMap.forEach((key, value) -> System.out::println);
    }
}

Key Methods of TreeMap

1. put(K key, V value): Associates the specified value with the specified key in this map.
2. remove(Object key): Removes the mapping for a key from this map if it is present.
3. get(Object key): Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
4. containsKey(Object key): Returns true if this map contains a mapping for the specified key.
5. containsValue(Object value): Returns true if this map maps one or more keys to the specified value.
6. size(): Returns the number of key-value mappings in this map.
7. isEmpty(): Returns true if this map contains no key-value mappings.
8. clear(): Removes all of the mappings from this map.
9. keySet(): Returns a Set view of the keys contained in this map.
10. values(): Returns a Collection view of the values contained in this map.
11. entrySet(): Returns a Set view of the mappings contained in this map.

NavigableMap Methods

As TreeMap implements the NavigableMap interface, it provides additional methods to navigate through the map:

1. lowerKey(K key): Returns the greatest key less than the given key, or null if there is no such key.
2. floorKey(K key): Returns the greatest key less than or equal to the given key, or null if there is no such key.
3. ceilingKey(K key): Returns the least key greater than or equal to the given key, or null if there is no such key.
4. higherKey(K key): Returns the least key greater than the given key, or null if there is no such key.
5. pollFirstEntry(): Retrieves and removes the first (lowest) entry, or returns null if the map is empty.
6. pollLastEntry(): Retrieves and removes the last (highest) entry, or returns null if the map is empty.
7. firstKey(): Returns the first (lowest) key currently in this map.
8. lastKey(): Returns the last (highest) key currently in this map.
9. subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive): Returns a view of the portion of this map whose keys range from fromKey to toKey.
10. headMap(K toKey, boolean inclusive): Returns a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey.
11. tailMap(K fromKey, boolean inclusive): Returns a view of the portion of this map whose keys are greater than (or equal to, if inclusive is true) fromKey.

TreeMap vs. HashMap

• Order: TreeMap maintains keys in a sorted order, while HashMap does not guarantee any specific order of keys.
• Performance: TreeMap operations have logarithmic time complexity, while HashMap operations have constant time complexity (O(1)) for basic operations, assuming a good hash function.
• Null Keys: TreeMap does not allow null keys, while HashMap allows one null key.
• Navigable Methods: TreeMap provides methods to navigate through the map, such as lowerKey, floorKey, ceilingKey, and higherKey, which HashMap does not provide.

Performance Considerations

• Logarithmic Time Complexity: TreeMap operations such as get, put, and remove have logarithmic time complexity (O(log n)).
• Memory Usage: TreeMap uses a Red-Black tree internally, which can consume more memory compared to a HashMap.

Conclusion

TreeMap is a powerful and flexible implementation of the NavigableMap interface, suitable for scenarios where a sorted map of key-value pairs is needed. Its ability to maintain order and provide navigable methods makes it an excellent choice for many applications. However, it’s important to consider the performance implications of using TreeMap compared to other map implementations like HashMap.