Cum se evaluează complexitatea temporală a operației de adăugare a unui element în TreeSet?

În Java, clasa TreeSet este implementată pe baza unui copac roșu-negru, care este un copac binar de căutare echilibrat. Complexitatea temporală a operației de adăugare a unui element în TreeSet este O(log n), unde n reprezintă numărul de elemente din mulțime.

Aceasta se datorează faptului că, pentru inserare, elementul este căutat mai întâi în copac pentru a determina poziția corectă, apoi se face echilibrarea copacului, ceea ce durează timp logaritmic.

Exemplu:

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