Какая сложность вставки элемента в TreeMap?

Сложность операций в TreeMap

Вставка элемента в TreeMap: O(log n)

Вставка элемента в TreeMap имеет временную сложность O(log n), где n — количество элементов в TreeMap. Это объясняется внутренней реализацией TreeMap на основе красно-чёрного дерева (Red-Black Tree).

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

TreeMap использует красно-чёрное дерево (Red-Black Tree) для хранения элементов. Red-Black Tree — это самобалансирующееся бинарное дерево поиска, которое гарантирует высоту дерева O(log n).

// Упрощённая внутренняя структура TreeMap
private static final class Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;      // Левое поддерево (меньшие ключи)
    Entry<K,V> right;     // Правое поддерево (большие ключи)
    Entry<K,V> parent;    // Родитель (для балансировки)
    boolean color;        // Красный (true) или чёрный (false)
}

private Entry<K,V> root;

Процесс вставки (put operation)

public class TreeMapInsertionExample {
    public static void main(String[] args) {
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        
        // Каждая вставка: O(log n) сложность
        treeMap.put(5, "five");      // O(log 1) = O(1) — первый элемент
        treeMap.put(3, "three");     // O(log 2)
        treeMap.put(7, "seven");     // O(log 3)
        treeMap.put(1, "one");       // O(log 4)
        treeMap.put(9, "nine");      // O(log 5)
        treeMap.put(4, "four");      // O(log 6)
        
        // Итоговое дерево (самобалансированное):
        //        5
        //       / \
        //      3   7
        //     / \   \
        //    1   4   9
    }
}

Детальный процесс вставки

Шаг 1: Поиск позиции (O(log n))

private Entry<K,V> getEntry(Object key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0)      // key меньше => идём влево
            p = p.left;
        else if (cmp > 0) // key больше => идём вправо
            p = p.right;
        else
            return p;     // Найдено!
    }
    return null;
}

Шаг 2: Вставка элемента

public V put(K key, V value) {
    Entry<K,V> t = root;
    
    if (t == null) {
        root = new Entry<>(key, value, null);
        size++;
        return null;
    }
    
    int cmp;
    Entry<K,V> parent;
    
    // Поиск правильной позиции (O(log n))
    do {
        parent = t;
        cmp = compare(key, t.key);
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
        else {
            // Ключ уже существует, обновляем значение
            V oldValue = t.value;
            t.value = value;
            return oldValue;
        }
    } while (t != null);
    
    // Создаём новый узел
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    
    // Балансирование дерева (O(log n))
    fixAfterInsertion(e);
    size++;
    return null;
}

Шаг 3: Балансирование (O(log n))

После вставки TreeMap проверяет и восстанавливает свойства красно-чёрного дерева:

private void fixAfterInsertion(Entry<K,V> x) {
    x.color = true;  // Новый узел красный
    
    while (x != null && x != root && x.parent.color) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            // Левая сторона дерева
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y)) {
                setColor(parentOf(x), false);
                setColor(y, false);
                setColor(parentOf(parentOf(x)), true);
                x = parentOf(parentOf(x));
            } else {
                // Требуется ротация
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), false);
                setColor(parentOf(parentOf(x)), true);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            // Аналогично для правой стороны
        }
    }
    setColor(root, false);
}

Сравнение сложности: TreeMap vs HashMap vs LinkedHashMap

Пример: Влияние размера на производительность

public class TreeMapPerformance {
    public static void main(String[] args) {
        // При n элементах, вставка требует O(log n) операций
        
        int n = 1_000_000;
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        
        long start = System.nanoTime();
        for (int i = 0; i < n; i++) {
            treeMap.put(i, "value-" + i);  // O(log n) за каждую операцию
        }
        long elapsed = System.nanoTime() - start;
        
        System.out.println("TreeMap insertion (" + n + " элементов): " + (elapsed / 1_000_000) + " ms");
        
        // Примерный расчёт:
        // log2(1_000_000) ≈ 20
        // 1_000_000 * 20 операций = 20_000_000
        // Обычно: 200-500 ms (зависит от CPU)
    }
}

// Для сравнения: HashMap
long start = System.nanoTime();
HashMap<Integer, String> hashMap = new HashMap<>();
for (int i = 0; i < 1_000_000; i++) {
    hashMap.put(i, "value-" + i);  // O(1) в среднем
}
long elapsed = System.nanoTime() - start;
System.out.println("HashMap insertion: " + (elapsed / 1_000_000) + " ms");
// Обычно: 50-100 ms (значительно быстрее)

Когда O(log n) медленнее, чем O(1)?

Для 1 миллиона элементов:

• O(1): 1 операция в худшем случае
• O(log n): log2(1,000,000) ≈ 20 операций

Таким образом, HashMap примерно в 20 раз быстрее для вставки.

Преимущества O(log n) сложности TreeMap

1. Упорядоченность

TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(5, "five");
treeMap.put(3, "three");
treeMap.put(7, "seven");

// Итерация в порядке возрастания ключей
for (Integer key : treeMap.keySet()) {
    System.out.println(key);  // 3, 5, 7
}

2. Range операции (O(log n) для начала, затем O(k)) где k — количество элементов в range

TreeMap<Integer, String> treeMap = new TreeMap<>();
for (int i = 1; i <= 10; i++) {
    treeMap.put(i, "value-" + i);
}

// subMap: O(log n) для поиска начала, O(k) для итерации
SortedMap<Integer, String> range = treeMap.subMap(3, 7);
for (Map.Entry<Integer, String> entry : range.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
    // 3, 4, 5, 6
}

3. headMap, tailMap

// Все элементы с ключом < 5: O(log n) для поиска
SortedMap<Integer, String> head = treeMap.headMap(5);

// Все элементы с ключом >= 5: O(log n) для поиска
SortedMap<Integer, String> tail = treeMap.tailMap(5);

// Первый/последний элемент: O(log n)
Integer firstKey = treeMap.firstKey();
Integer lastKey = treeMap.lastKey();

Красно-чёрное дерево: почему O(log n) гарантировано?

Красно-чёрное дерево гарантирует, что высота дерева не превышает 2 * log2(n + 1):

Свойства красно-чёрного дерева:
1. Каждый узел — красный или чёрный
2. Корень — чёрный
3. Все листья (null) — чёрные
4. Красные узлы имеют только чёрных потомков
5. Все пути от узла до листьев содержат одинаковое количество чёрных узлов

Эти свойства гарантируют, что дерево остаётся относительно сбалансированным,
потому высота ≤ 2 * log2(n)

Практический выбор между HashMap и TreeMap

// Выбери HashMap, если:
// - Нужна максимальная скорость вставки/удаления/поиска (O(1))
// - Не нужна упорядоченность
Map<Integer, String> map = new HashMap<>();

// Выбери TreeMap, если:
// - Нужна упорядоченность по ключам
// - Нужны range операции (subMap, headMap, tailMap)
// - Можешь позволить O(log n) вместо O(1)
SortedMap<Integer, String> map = new TreeMap<>();

// LinkedHashMap: компромисс (O(1) + порядок вставки)
Map<Integer, String> map = new LinkedHashMap<>();

Заключение

Сложность вставки элемента в TreeMap — O(log n), что обеспечивается использованием красно-чёрного дерева. Это медленнее, чем HashMap (O(1)), но даёт упорядоченность и возможность range операций. Выбирай структуру в зависимости от требований приложения.