Qual è la complessità dell'algoritmo di inserimento (put) in TreeMap?

In Java, la classe TreeMap è implementata su un albero rosso-nero, un albero binario di ricerca bilanciato.

La complessità dell'operazione di inserimento (put) in TreeMap è O(log n), dove n è il numero di elementi nella mappa.

Ciò è dovuto al fatto che per inserire bisogna:

• Trovare la posizione per la nuova chiave (ricerca nell'albero) — O(log n).
• Inserire l'elemento e, se necessario, eseguire il bilanciamento dell'albero (rotazioni e ricolorazioni) — anche O(log n) nel caso peggiore.

Pertanto, l'inserimento in TreeMap è efficiente e scalabile grazie alla sua struttura dati bilanciata.