Aká je zložitosť algoritmu vkladania (put) v TreeMap?

V Jave je trieda TreeMap implementovaná na základe červeno-čierneho stromu, vyváženého binárneho vyhľadávacieho stromu.

Zložitosť operácie vloženia (put) v TreeMap je O(log n), kde n je počet prvkov v mape.

To je spôsobené tým, že na vloženie je potrebné:

• Nájsť pozíciu pre nový kľúč (vyhľadávanie v strome) — O(log n).
• Vložiť prvok a v prípade potreby vyvážiť strom (rotácie a prefarbenie) — tiež O(log n) v najhoršom prípade.

Preto je vkladanie do TreeMap efektívne a škálovateľné vďaka vyváženej dátovej štruktúre.