Jaká je složitost algoritmu vložení (put) v TreeMap?

V jazyce Java je třída TreeMap implementována na základě červené-černé stromu, vyváženého binárního vyhledávacího stromu.

Složitost operace vložení (put) v TreeMap je O(log n), kde n je počet prvků v mapě.

To je způsobeno tím, že pro vložení je třeba:

• Najít pozici pro nový klíč (vyhledávání ve stromu) — O(log n).
• Vložit prvek a v případě potřeby provést vyvážení stromu (rotace a přebarvení) — také O(log n) v nejhorším případě.

Tím je vkládání do TreeMap efektivní a škálovatelné díky vyvážené struktuře dat.