Care este complexitatea algoritmului de inserție (put) în TreeMap?

În Java, clasa TreeMap este implementată pe baza unui copac roșu-negru, un copac binar de căutare echilibrat.

Complexitatea operației de inserare (put) în TreeMap este O(log n), unde n este numărul de elemente din hartă.

Acest lucru se datorează faptului că pentru inserare trebuie:

• Să găsești poziția pentru cheia nouă (căutare în copac) — O(log n).
• Să inserezi elementul și, dacă este necesar, să echilibrezi copacul (rotații și re-colorare) — tot O(log n) în cel mai rău caz.

Prin urmare, inserarea în TreeMap este eficientă și scalabilă datorită structurii sale de date echilibrate.