Kā tiek novērtēta elementa pievienošanas operācijas laika sarežģītība TreeSet?

Java valodā TreeSet klase ir īstenota, balstoties uz sarkano-melno koku, kas ir līdzsvarots binārais meklēšanas koks. Operācijas pievienot elementu TreeSet laika sarežģītība ir O(log n), kur n ir elementu skaits kopā.

Tas ir tāpēc, ka, pievienojot elementu, vispirms tas tiek meklēts kokā, lai noteiktu pareizo vietu, un pēc tam tiek veikta koka līdzsvarošana, kas aizņem logaritmisku laiku.

Piemērs:

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