Quel algorithme est utilisé pour rechercher un élément dans TreeMap et à quel point est-il efficace?

TreeMap en Java est implémenté sur un arbre rouge-noir, qui est une variante d'arbre binaire de recherche équilibré. Pour rechercher un élément, un algorithme de recherche binaire dans l'arbre est utilisé, qui grâce à l'équilibrage maintient la hauteur de l'arbre approximativement égale à (O(\log n)).

Cela garantit une recherche, une insertion et une suppression efficaces en temps (O(\log n)), beaucoup plus rapide que la recherche linéaire dans une structure non triée.

Exemple d'utilisation de TreeMap:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "dix");
map.put(5, "cinq");
map.put(20, "vingt");

String value = map.get(10); // recherche par clé 10 en O(log n)