Jak ocenia się złożoność czasową operacji dodawania elementu do TreeSet?

W Javie klasa TreeSet jest zaimplementowana na podstawie drzewa czerwono-czarnego, które jest zbalansowanym drzewem binarnym wyszukiwania. Złożoność czasowa operacji dodania elementu do TreeSet wynosi O(log n), gdzie n to liczba elementów w zbiorze.

Jest to związane z tym, że podczas dodawania elementu najpierw jest on wyszukiwany w drzewie, aby określić właściwe miejsce, a następnie przeprowadzane jest balansowanie drzewa, co zajmuje czas logarytmiczny.

Przykład:

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