Come viene valutata la complessità temporale dell'operazione di aggiunta di un elemento in TreeSet?

In Java, la classe TreeSet è implementata su un albero rosso-nero, che è un albero binario di ricerca bilanciato. La complessità temporale dell'operazione di aggiunta di un elemento a TreeSet è O(log n), dove n è il numero di elementi nell'insieme.

Ciò è dovuto al fatto che, per inserire un elemento, si cerca prima nel albero per determinare la posizione corretta, e poi si effettua un bilanciamento dell'albero, che richiede tempo logaritmico.

Esempio:

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