Hoe wordt de tijdcomplexiteit van de bewerking van het toevoegen van een element aan TreeSet geëvalueerd?

In Java is de TreeSet-klasse geïmplementeerd op basis van een rood-zwart boom, dat een gebalanceerde binaire zoekboom is. De tijdscomplexiteit van de operatie om een element toe te voegen aan TreeSet is O(log n), waarbij n het aantal elementen in de verzameling is.

Dit komt doordat, bij het invoegen van een element, eerst in de boom wordt gezocht om de juiste plaats te bepalen, en vervolgens wordt de boom in balans gebracht, wat logaritmische tijd kost.

Voorbeeld:

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