En Java, la classe TreeSet est implémentée sur un arbre rouge-noir, qui est un arbre binaire de recherche équilibré. La complexité temporelle de l'opération d'ajout d'un élément à TreeSet est O(log n), où n est le nombre d'éléments dans l'ensemble.

Cela est dû au fait que, pour insérer un élément, on le recherche d'abord dans l'arbre pour déterminer la position correcte, puis on effectue un équilibrage de l'arbre, ce qui prend un temps logarithmique.

Exemple:

TreeSet<Integer> set = new TreeSet<>();
set.add(10); // O(log n)
set.add(5);  // O(log n)
set.add(20); // O(log n)

Précédent Suivant