Quelle est la complexité de l'algorithme d'insertion (put) dans TreeMap?

En Java, la classe TreeMap est implémentée sur un arbre rouge-noir, un arbre binaire de recherche équilibré.

La complexité de l'opération d'insertion (put) dans TreeMap est O(log n), où n est le nombre d'éléments dans la carte.

Cela est dû au fait que pour insérer, il faut:

• Trouver la position pour la nouvelle clé (recherche dans l'arbre) — O(log n).
• Insérer l'élément et, si nécessaire, effectuer un équilibrage de l'arbre (rotations et recolorations) — aussi O(log n) dans le pire des cas.

Ainsi, l'insertion dans TreeMap est efficace et évolutive grâce à sa structure de données équilibrée.