Как оценивается временная сложность операции добавления элемента в 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)