Kaip įvertinama operacijos pridėti elementą į TreeSet laiko sudėtingumas?

Java kalboje TreeSet klasė įgyvendinta remiantis raudonojo-juodojo medžio struktūra, kuris yra subalansuotas dvejetainis paieškos medis. Operacijos pridėti elementą į TreeSet laiko sudėtingumas yra O(log n), kur n yra elementų skaičius rinkinyje.

Tai susiję su tuo, kad įterpiant elementą, pirmiausia ieškoma medyje, kad būtų nustatyta teisinga vieta, o tada atliekamas medžio balansavimas, kuris užtrunka logaritminį laiką.

Pavyzdys:

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