Kako se procenjuje vremenska složenost operacije dodavanja elementa u TreeSet?

У Јави, класа 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)