What is TreeMap in Java

TreeMap is a sorted map implementation based on a red-black tree. The elements are sorted by their keys, which are inserted into the map using the put() method or can be specified in the constructor.
The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

So what is red-black tree?

A red-black tree is a self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the color (red or black) of the node.
These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.
There is a perfect balance when all the leaves are at the same level, and there is no empty space between the leaves.
In, this post, our focus is on TreeMap and TreeSet and not on Tree itself.

Thread Safety in TreeMap

TreeMap is not thread-safe. If multiple threads access a TreeMap concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.)
This is typically accomplished by synchronizing on some object that naturally encapsulates the map.
Read More on the safety...

TreeMap vs HashMap

HashMap is not sorted while TreeMap is sorted by keys. TreeMap is slower than HashMap because it has to keep the elements in sorted order. TreeMap is not thread-safe while HashMap is thread-safe. HashMap allows one null key and any number of null values while TreeMap doesn't allow any null keys or values.

How to use TreeMap in Java

Create TreeMap

TreeMap<String, Integer> map = new TreeMap<>();

Add elements to TreeMap

map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

Initialize TreeMap Comparator

TreeMap<String, Integer> map = new TreeMap<>(new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        return o2.compareTo(o1);
    }
});

Comparator test case

@Test
public void treeComparatoTest() {
    TreeMap<Integer, String> mp =new TreeMap<>(Comparator.reverseOrder());
    mp.put(1, "fas based");
    mp.put(5, "fas three");
    mp.put(4, "fas fix");
    mp.put(3, "fas abc");
    mp.put(2, "fas learning");
    assertEquals("[5, 4, 3, 2, 1]", mp.keySet().toString());
}

This indicates we use all forms of the compareTo() method to compare the keys in the map like priority queue.

Common TreeMap Methods

Method	Description
clear()	Removes all of the mappings from this map.
containsKey(Object key)	Returns true if this map contains a mapping for the specified key.
containsValue(Object value)	Returns true if this map maps one or more keys to the specified value.
entrySet()	Returns a Set view of the mappings contained in this map.
firstKey()	Returns the first (lowest) key currently in this map.
get(Object key)	Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
headMap(K toKey)	Returns a view of the portion of this map whose keys are strictly less than toKey.
isEmpty()	Returns true if this map contains no key-value mappings.
keySet()	Returns a Set view of the keys contained in this map.
lastKey()	Returns the last (highest) key currently in this map.
put(K key, V value)	Associates the specified value with the specified key in this map.
remove(Object key)	Removes the mapping for the specified key from this map if present.
size()	Returns the number of key-value mappings in this map.
subMap(K fromKey, K toKey)	Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.
tailMap(K fromKey)	Returns a view of the portion of this map whose keys are greater than or equal to fromKey.
values()	Returns a Collection view of the values contained in this map.

Problem Solving With TreeMap

1. My Calendar III

k-booking between all the previous events. Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

Solution 1 with No TreeMap

In this case, we generate the times for our interval checks.From the start point we add 1 and from the end point we subtract 1. We then iterate through the times and keep a running total of the number of events. If the running total is greater than k, we return false. If we reach the end of the times array, we return true.

        int[] time; 
        public MyCalendarThree() {
            time = new int[1000001];
        }

        public int book(int start, int end) {
            time[start]++;
            time[end]--;
            int res = 0, cur = 0;
            for (int i = 0; i < 1000001; i++) {
                cur += time[i];
                res = Math.max(res, cur);
            }
            return res;
        }

Solution 2 with TreeMap

In this case, we use a TreeMap to keep track of the number of events at each time. We then iterate through the TreeMap and keep a running total of the number of events. If the running total is greater than k, we return false. If we reach the end of the TreeMap, we return true.

class MyCalendarThree {
    TreeMap<Integer, Integer> map;
    public MyCalendarThree() {
        map = new TreeMap<>();
    }

    public int book(int start, int end) {
        map.put(start, map.getOrDefault(start, 0) + 1);
        map.put(end, map.getOrDefault(end, 0) - 1);
        int count = 0, max = 0;
        for (int v : map.values()) {
            count += v;
            max = Math.max(max, count);
        }
        return max;
    }
}

book method explanation

map.put(start, map.getOrDefault(start, 0) + 1);
map.put(end, map.getOrDefault(end, 0) - 1);

we put the first and the end time into our tree map. The value of the start time is 1 and the value of the end time is -1. This is because we want to know how many events are happening at a certain time. If the value is 1, it means that there is an event starting at that time. If the value is -1, it means that there is an event ending at that time. If the value is 0, it means that there is no event happening at that time.

int count = 0, max = 0;
for (int v : map.values()) {
    count += v;
    max = Math.max(max, count);
}

We use a for loop to iterate through all the values in the map. We use a variable count to keep track of the number of events happening at a certain time. We use a variable max to keep track of the maximum number of events happening at a certain time. We update the count and max at each time.

Why we used TreeMap

We used tree map because we know the order of start and end times in the input. We can use a tree map to keep track of the number of events happening at a certain time. We can use a tree map to keep track of the maximum number of events happening at a certain time.

References

• TreeMap
• TreeMap in Java
• TreeMap in Java
• TreeMap Not ThreadSafe