Ako sa hodnotí časová zložitosť operácie pridania prvku do TreeSet?

V jazyku Java je trieda TreeSet implementovaná na základe červeno-čierneho stromu, ktorý je vyváženým binárnym vyhľadávacím stromom. Časová zložitosť operácie pridania prvku do TreeSet je O(log n), kde n je počet prvkov v množine.

To je spôsobené tým, že pri vkladaní prvku sa najskôr hľadá v strome, aby sa určila správna pozícia, a potom sa strom vyváži, čo trvá logaritmický čas.

Príklad:

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