Why treemap takes O(log(n)) time in Get/put

Question

In one of the posts I saw that TreeMap takes O(log(n)) time for get/put. Can someone please answer why it takes O(log(n)), even when it can search directly through get/put using key?

Flaggy

How many operations do you think it takes to search directly? – Eudemonism

You should check the algorithms in the book that are referred by the Javadoc of the Treemap class, instead of asking here in an inappropriate format. – Sodium

Answer 1

In a TreeMap, the key/value entries are stored in a Red-Black tree, and in order to find if a key is contained in the tree, you have to traverse it from the root, down some path, until reaching the required key or reaching a leaf.

A tree containing n elements has an O(log n) height, and therefore that's the time it would take to search for a key.

Zackaryzacks

but the op asked why O(log(n))? – Optimistic

@KickButtowski I had a typo in my original version. Fixed now. – Zackaryzacks

I think it does not hurt to say red black tree which is kind of balanced tree – Optimistic