Как се оценява времевата сложност на операцията по добавяне на елемент в TreeSet?

В Java класът TreeSet е реализиран на базата на червено-черен дърво, което е балансирано двоично дърво за търсене. Времевата сложност на операцията за добавяне на елемент към TreeSet е O(log n), където n е броят на елементите в множеството.

Това се дължи на факта, че при добавяне на елемент първо се търси в дървото, за да се определи правилното място, а след това се извършва балансировка на дървото, което отнема логаритмично време.

Пример:

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