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

Сложность удаления элемента в TreeMap

Прямой ответ: O(log n)

Операция удаления (remove) в TreeMap выполняется за O(log n) — логарифмическое время, где n — количество элементов в мап.

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

TreeMap построена на Red-Black Tree (красно-чёрное дерево):

TreeMap — это сбалансированное двоичное дерево поиска
Красные и чёрные узлы поддерживают баланс
Высота дерева = O(log n)

       20 (B)
      /      \
    10 (R)   30 (R)
    /   \    /    \
   5(B) 15(B) 25(B) 35(B)

Высота дерева из 7 элементов = log2(7) ≈ 3

Анализ операции remove()

Шаги удаления в TreeMap:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "ten");
map.put(20, "twenty");
map.put(30, "thirty");

map.remove(20);  // O(log n) операция

Что происходит:

1. Поиск узла — O(log n): идём по дереву вверх-вниз
2. Удаление узла — O(1): удаляем найденный узел
3. Ребалансирование — O(log n): ротации и переоткраски

Итого: O(log n)

Визуализация процесса удаления

До удаления (20):
       20 (B)
      /      \
    10 (R)   30 (R)

Шаг 1: Найти узел 20
Шаг 2: Удалить узел
Шаг 3: Ребалансировать дерево
Шаг 4: Переокрасить узлы

После удаления:
       30 (B)
      /
    10 (R)

Сравнение с другими структурами

Практический пример

public class TreeMapComplexity {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        
        // Добавляем элементы (также O(log n) каждое)
        for (int i = 0; i < 1000; i++) {
            map.put(i, "value" + i);  // O(log n)
        }
        
        // Удаление: O(log n)
        long start = System.nanoTime();
        map.remove(500);  // Удаляем элемент из середины
        long time1 = System.nanoTime() - start;
        System.out.println("Удаление 1 элемента: " + time1 + " нс");
        
        // Удаление первого элемента: O(log n)
        start = System.nanoTime();
        map.remove(0);
        long time2 = System.nanoTime() - start;
        System.out.println("Удаление первого: " + time2 + " нс");
        
        // Удаление последнего элемента: O(log n)
        start = System.nanoTime();
        map.remove(999);
        long time3 = System.nanoTime() - start;
        System.out.println("Удаление последнего: " + time3 + " нс");
        
        // Все примерно одинаковые времена!
        // Потому что все это O(log n)
    }
}

Внутренняя структура (упрощённо)

// Red-Black Tree Node в TreeMap
private static class Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;     // Левый потомок
    Entry<K,V> right;    // Правый потомок
    Entry<K,V> parent;   // Родительский узел
    boolean color;       // RED или BLACK
}

// Процесс удаления
public V remove(Object key) {
    Entry<K,V> p = getEntry(key);  // O(log n): поиск узла
    if (p == null)
        return null;
    
    V oldValue = p.value;
    deleteEntry(p);                // O(log n): удаление + ребалансирование
    return oldValue;
}

private void deleteEntry(Entry<K,V> p) {
    // Найти заменяющий узел
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);  // O(log n)
        p.key = s.key;
        p.value = s.value;
        p = s;
    }
    
    // Удалить узел и ребалансировать
    Entry<K,V> replacement = (p.left != null) ? p.left : p.right;
    
    if (replacement != null) {
        replacement.parent = p.parent;
        if (p.parent == null) {
            root = replacement;  // Новый корень
        } else if (p == p.parent.left) {
            p.parent.left = replacement;
        } else {
            p.parent.right = replacement;
        }
        
        // Ребалансирование дерева: O(log n) ротаций
        fixAfterDeletion(replacement);
    } else {
        fixAfterDeletion(p);
    }
}

Худший случай: сбалансированность

TreeMap ВСЕГДА остаётся сбалансированным:

❌ Несбалансированное дерево (как простой BST):
1
 \\  
  2
   \\
    3
     \\
      4
       \\
        5
Высота = 5, удаление = O(n) ✗

✓ Red-Black Tree (TreeMap):
      3 (B)
     /   \\
   2 (R)  4 (R)
   /       \\
  1 (B)   5 (B)

Высота = 3, удаление = O(log 5) ✓

Сравнение производительности

public class MapRemovePerformance {
    public static void main(String[] args) {
        // TreeMap: O(log n)
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        for (int i = 0; i < 1_000_000; i++) {
            treeMap.put(i, i);
        }
        
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10_000; i++) {
            treeMap.remove(i);
        }
        System.out.println("TreeMap.remove(10k): " + 
            (System.currentTimeMillis() - start) + " ms");
        // ~100-200 ms
        
        // HashMap: O(1) average
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < 1_000_000; i++) {
            hashMap.put(i, i);
        }
        
        start = System.currentTimeMillis();
        for (int i = 0; i < 10_000; i++) {
            hashMap.remove(i);
        }
        System.out.println("HashMap.remove(10k): " + 
            (System.currentTimeMillis() - start) + " ms");
        // ~20-50 ms (много быстрее)
    }
}

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

✓ Используй TreeMap когда:

• Нужна сортировка элементов
• Нужны методы типа first(), last(), subMap()
• Нужна итерация в порядке сортировки
• Нужен NavigableMap interface

TreeMap<Integer, String> map = new TreeMap<>();
map.put(30, "thirty");
map.put(10, "ten");
map.put(20, "twenty");

// Методы, которые работают благодаря порядку
Integer firstKey = map.firstKey();              // 10
Integer lastKey = map.lastKey();                // 30
Map.Entry<Integer, String> first = map.firstEntry();  // (10, "ten")
NavigableMap<Integer, String> sub = map.subMap(10, 30);  // [10, 30)

// Итерация в порядке (благодаря Red-Black Tree)
for (Integer key : map.keySet()) {
    System.out.println(key);  // 10, 20, 30 (отсортировано)
}

✗ Используй HashMap если:

• Не нужна сортировка
• Нужна максимальная производительность
• Часто добавляешь/удаляешь элементы

Таблица операций TreeMap

Выводы

✓ remove() в TreeMap = O(log n) логарифмическое время ✓ Гарантировано для любого элемента (нет худшего случая) ✓ Благодаря Red-Black Tree сбалансированности ✓ Медленнее чем HashMap (O(1)), но элементы отсортированы ✓ Идеален когда нужен порядок + быстрые операции