TreeMap collection views iterators time-complexity?

Question

Time-complexity of all 3 collection view iterators for HashMap (myHashMap.entrySet().iterator().next() and myHashMap.keySet().iterator().next() and myHashMap.values().iterator().next()) is well-documented in javadoc, it is O(n+c) for all those 3 iterators (n is number of mappings, c is capacity that is physical number of buckets in hashtable).

But what about respective 3 iterators of 3 respective TreeMap collection views? Nothing is said in official javadoc. What are their complexities? I did look in SE8 source code but I cannot judge from there.

Answer 1

Try to answer this based on these great comments:

1. One single next() call has a totally different time complexity compared with the whole iterating process.

2. TreeMap in Java is based on Red-Black Tree, which is a balanced binary search tree.

Refer to https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html

3. Iterating a whole TreeMap should have the same time complexity as traversing the Red-Balck Tree(For pre-order in-order or post-order traveral). So time complexity should be O(n) where n is the key(or value, or key-value mapping) count.

4. For a single next call, we can do it in O(1). If a whole O(n) time complexity is true, this should be trivial.