Какая скорость добавления в TreeSet?

Временная сложность добавления в TreeSet

Прямой ответ

TreeSet добавляет элементы за O(log n) — логарифмическое время, где n — количество элементов в наборе.

Почему O(log n)?

TreeSet внутри использует Red-Black Tree (красно-чёрное дерево) — саморегулирующееся бинарное дерево поиска. При добавлении элемента алгоритм:

1. Ищет правильное место для элемента — O(log n)
2. Вставляет элемент — O(1)
3. Балансирует дерево через ротации — O(log n)

Итого: O(log n) + O(1) + O(log n) = O(log n)

// Пример: добавление элемента в TreeSet
TreeSet<Integer> treeSet = new TreeSet<>();

treeSet.add(50);  // O(log n) — вставляется корень
treeSet.add(30);  // O(log n) — ищется место, вставляется
treeSet.add(70);  // O(log n) — может произойти балансировка
treeSet.add(20);  // O(log n)

System.out.println(treeSet); // [20, 30, 50, 70] — отсортировано!

Сравнение с другими коллекциями

Детали Red-Black Tree в TreeSet

Red-Black Tree — это бинарное дерево поиска с дополнительным свойством цвета узлов:

// TreeSet внутренне использует NavigableMap с TreeMap
public class TreeSet<E> extends AbstractSet<E>
        implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    // Внутренняя реализация через TreeMap
    private transient NavigableMap<E, Object> m;
    // ...
}

// TreeMap использует красно-чёрное дерево
class TreeMap<K, V> extends AbstractMap<K, V>
        implements NavigableMap<K, V>, Cloneable, java.io.Serializable
{
    // Узел дерева
    static final class Entry<K, V> implements Map.Entry<K, V> {
        K key;
        V value;
        Entry<K, V> left;
        Entry<K, V> right;
        Entry<K, V> parent;
        boolean color = BLACK;
        // ...
    }
}

Практический пример: производительность

import java.util.*;

public class TreeSetPerformance {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        
        // Добавление 1 млн элементов
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1_000_000; i++) {
            treeSet.add(i);
        }
        long duration = System.currentTimeMillis() - start;
        System.out.println("TreeSet (1M элементов): " + duration + "ms");
        // Примерный результат: 150-250ms
        
        // Логика: 1M элементов * log2(1M) ≈ 20 млн операций
        // На современном процессоре это 100-300ms
    }
}

Когда использовать TreeSet

Используй TreeSet, когда нужна сортировка:

TreeSet<String> words = new TreeSet<>();
words.add("zebra");
words.add("apple");
words.add("banana");

System.out.println(words); // [apple, banana, zebra] — автосортировка!

Используй TreeSet для диапазонных запросов:

TreeSet<Integer> scores = new TreeSet<>();
scores.addAll(Arrays.asList(10, 30, 50, 70, 90));

// Получить элементы от 30 до 70
NavigableSet<Integer> range = scores.subSet(30, true, 70, true);
System.out.println(range); // [30, 50, 70]

// Получить элементы меньше 50
NavigableSet<Integer> less = scores.headSet(50, false);
System.out.println(less); // [10, 30]

// Получить элементы больше 50
NavigableSet<Integer> greater = scores.tailSet(50, true);
System.out.println(greater); // [50, 70, 90]

Когда не использовать TreeSet

Используй HashSet, если сортировка не нужна:

HashSet<String> fastSet = new HashSet<>();
fastSet.add("zebra");   // O(1)
fastSet.add("apple");   // O(1)
fastSet.add("banana");  // O(1)
// HashSet быстрее на операциях добавления (O(1) вместо O(log n))

Итог

• TreeSet.add() = O(log n) из-за красно-чёрного дерева
• Автоматическая сортировка элементов
• Поддерживает диапазонные операции (subSet, headSet, tailSet)
• Медленнее HashSet на операциях добавления/удаления, но данные всегда отсортированы
• Используй для отсортированных данных или когда нужны диапазонные запросы