TreeMap lastKey lookup time

Question

What is the time complexity of TreeMap.lastKey() part of the SortedMap interface?

The oracle docs mention this about TreeMaps:

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

Hyponitrite

It should be O(log(n)) too. It is mostly balanced and requires going to the right always. – Cortisol

You can also look at the source code, to see how it's implemented. The answer would be pretty straightforward after. – Bhang

I see. Is there an elegant way to always keep track of the last key/value even after deleting an object from the map? Maybe with the maps entrySet? – Hyponitrite

@ArjunPatel Is O(logn) too large? What is your usecase? – Cortisol

You can track the map's maximum key by wrapping / instrumenting all the map's mutation methods (don't forget the iterator's remove() method and the mutators of the submaps, and their iterators and submaps, etc.). That's certainly not elegant, though, and it will degrade performance, especially of the multi-element removal methods. – Yodle

Answer 1

According to the implementation in the Open JDK, it is O(log N):

public K lastKey() {
    return key(getLastEntry());
}
final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}

The lastKey() calls getLastEntry(), which continues to take the right subtree until there are no further nodes to take. Since the implementation maintains the tree in a balanced state, the number of iterations is O(log N).

Torres

It's easy to make the intuitive mistake that the last entry would be easily accessible at the "end" of the data structure. I had to remind myself that the "easily accessible" entry for a red-black tree is actually the median element (i.e., the element at the root of the tree). – Angeli

Answer 2

If TreeMap can guarantee O(log(n)) for containsKey() (as it does), then it should be able to do lastKey() in O(log(n)) as well. Any tree structure that can be certain to yield O(log(n)) key lookups can also support finding the maximum key in O(log(n)).

Although nothing inherently rules out a brain-dead implementation that does worse, I think it's pretty safe to discount that possibility for java.util.TreeMap.

Yodle