TreeMap - Notes By ShariqSP

TreeMap in Java

TreeMap is an implementation of the SortedMap interface in Java that stores key-value pairs in sorted order based on the natural ordering of keys or a custom comparator. It uses a Red-Black tree data structure to maintain the elements in sorted order, providing efficient retrieval and insertion operations.

Definition:

A TreeMap is a collection that stores key-value pairs in a sorted manner. It does not allow duplicate keys, but allows null values. Elements are stored based on the natural ordering of keys or a custom comparator provided by the user.

Methods:

  • put(K key, V value): Associates the specified value with the specified key in the map.
  • get(Object key): Returns the value associated with the specified key, or null if the key is not present in the map.
  • remove(Object key): Removes the mapping for the specified key from the map, if present.
  • containsKey(Object key): Returns true if the map contains a mapping for the specified key.
  • isEmpty(): Returns true if the map contains no key-value mappings.
  • size(): Returns the number of key-value mappings in the map.
  • clear(): Removes all key-value mappings from the map.

Example:


            import java.util.TreeMap;

            public class Main {
                public static void main(String[] args) {
                    // Create a TreeMap of integers
                    TreeMap map = new TreeMap<>();

                    // Add key-value pairs to the map
                    map.put(3, "Java");
                    map.put(1, "Python");
                    map.put(2, "C++");

                    // Display the map
                    System.out.println("Elements in the map:");
                    System.out.println(map);

                    // Remove a key-value pair
                    map.remove(1);

                    // Display the modified map
                    System.out.println("\nElements after removal:");
                    System.out.println(map);
                }
            }

In this example, a TreeMap is created to store key-value pairs of integers and strings. Key-value pairs are added to the map using the put() method, and a key-value pair is removed using the remove() method.

Advantages and Disadvantages of TreeMap

Advantages:

  • Sorted Order: TreeMap maintains the elements in sorted order based on the natural ordering of keys or a custom comparator. This makes TreeMap suitable for scenarios where elements need to be accessed in a sorted manner.
  • Efficient Operations: TreeMap offers efficient performance for operations like insertion, deletion, and retrieval of elements. The time complexity of these operations is O(log n), where n is the number of elements in the TreeMap.
  • Search Operations: TreeMap provides efficient search operations, including finding the minimum and maximum elements, and navigating through the elements in ascending or descending order.
  • Implements NavigableMap: TreeMap implements the NavigableMap interface, which provides additional navigation methods, such as ceiling, floor, higher, and lower, for locating elements based on their keys.

Disadvantages:

  • Memory Overhead: TreeMap requires additional memory to maintain the balanced tree structure, resulting in higher memory consumption compared to simpler data structures like HashMap.
  • Complexity: The internal structure of TreeMap, typically a balanced binary search tree, introduces complexity in terms of implementation and understanding. This complexity may impact performance and require additional maintenance.
  • Slower Operations: While TreeMap offers efficient operations, the time complexity of O(log n) may be slower compared to simpler data structures like HashMap for certain scenarios, especially when the number of elements is large.
  • Limitation on Keys: TreeMap requires keys to be mutually comparable, either through their natural ordering or a custom comparator. This limitation may restrict the types of keys that can be used in TreeMap.

Interview Questions and MCQs on TreeMap in Java

Interview Questions:

  1. What is a TreeMap in Java?
  2. How does TreeMap differ from HashMap and LinkedHashMap?
  3. What is the significance of natural ordering in TreeMap?
  4. How is TreeMap implemented internally?
  5. Can TreeMap contain duplicate keys?
  6. How do you add key-value pairs to a TreeMap?
  7. How do you remove key-value pairs from a TreeMap?
  8. What are the advantages and disadvantages of using TreeMap?

Multiple Choice Questions (MCQs):

  1. Which interface does TreeMap implement?
    a) List
    b) Set
    c) Map
    d) Collection
    Answer: c) Map
  2. How are key-value pairs stored internally in a TreeMap?
    a) Based on their hash codes
    b) Based on their indexes
    c) In natural order
    d) In insertion order
    Answer: c) In natural order
  3. What happens when you try to add a key-value pair with a duplicate key to a TreeMap?
    a) The key-value pair is added without any changes
    b) An exception is thrown
    c) The existing value associated with the key is replaced with the new one
    d) The new key-value pair is ignored
    Answer: c) The existing value associated with the key is replaced with the new one
  4. Which method is used to remove all key-value pairs from a TreeMap?
    a) removeAll()
    b) clear()
    c) deleteAll()
    d) erase()
    Answer: b) clear()
  5. How do you check if a TreeMap contains a specific key?
    a) containsKey()
    b) contains()
    c) containsValue()
    d) hasKey()
    Answer: a) containsKey()
☰