Какая сложность доступа по ключу в TreeMap?

Сложность доступа по ключу в TreeMap

TreeMap в Java основана на красно-чёрном дереве (Red-Black Tree) и имеет логарифмическую сложность O(log n) для операций get, put и remove. Это важное отличие от HashMap, которая имеет O(1) в среднем случае.

TreeMap структура

TreeMap — это отсортированная карта, которая хранит элементы в упорядоченном виде. Она основана на самобалансирующемся двоичном дереве поиска (красно-чёрном дереве).

        TreeMap (отсортирована)
             ↓
        Red-Black Tree
             ↓
           (50)
          /    \
        (25)   (75)
        / \     / \
      (10)(40)(60)(90)

Временная сложность TreeMap

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

TreeMap<Integer, String> map = new TreeMap<>();

// Вставка — O(log n)
map.put(50, "fifty");     // O(log n)
map.put(25, "twenty-five"); // O(log n)
map.put(75, "seventy-five"); // O(log n)
map.put(10, "ten");       // O(log n)

// Получение — O(log n)
String value = map.get(25);  // O(log n) — нужно спуститься по дереву

// Проверка наличия — O(log n)
boolean contains = map.containsKey(50);  // O(log n)

// Удаление — O(log n)
map.remove(25);  // O(log n) — нужно найти и удалить с перебалансировкой

// Специальные операции — O(1)
Integer firstKey = map.firstKey();    // O(1) — крайний левый элемент
Integer lastKey = map.lastKey();      // O(1) — крайний правый элемент

// Подмножество — O(1)
SortedMap<Integer, String> submap = map.subMap(25, 75);  // O(1)

Сравнение HashMap vs TreeMap

// HashMap
HashMap<Integer, String> hashMap = new HashMap<>();
hashMap.put(50, "fifty");   // O(1) в среднем случае
hashMap.get(50);            // O(1) в среднем случае
hashMap.remove(50);         // O(1) в среднем случае
// Элементы НЕ отсортированы!
// Порядок: 75, 25, 50, 10 (случайный)

// TreeMap
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(50, "fifty");   // O(log n)
treeMap.get(50);            // O(log n)
treeMap.remove(50);         // O(log n)
// Элементы ОТСОРТИРОВАНЫ!
// Порядок: 10, 25, 50, 75 (по возрастанию ключей)

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

Красно-чёрное дерево поддерживает высоту дерева O(log n), это означает:

  n элементов → высота ≈ log₂(n)
  
  n = 1000000 → высота ≈ 20 уровней
  
Для поиска нужно спуститься на 20 уровней максимум
Каждый уровень — O(1) операция
Итого: 20 * O(1) = O(log n)

Красно-чёрное дерево

Свойства красно-чёрного дерева:

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

Эти правила гарантируют, что дерево остаётся сбалансированным, что обеспечивает O(log n) высоту.

Визуализация операции get() в TreeMap

TreeMap содержит: {10, 25, 50, 75, 90}

Поиск: map.get(25)

         (50) ← начинаем здесь
        /    \
      (25)   (75)  ← идём влево, потому что 25 < 50
      /  \      
    (10) (40)  
         ↑
      Нашли! 25 == 25
      
Шаги:
1. Сравнить 25 с 50 → 25 < 50, идём влево — O(1)
2. Сравнить 25 с 25 → 25 == 25, найдено — O(1)

Всего шагов: 2 = log₂(5) ≈ 2.3, поэтому O(log n)

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

import java.util.*;

public class MapPerformanceTest {
    public static void main(String[] args) {
        testMap(new HashMap<>(), "HashMap");
        testMap(new TreeMap<>(), "TreeMap");
    }
    
    static void testMap(Map<Integer, String> map, String name) {
        final int SIZE = 1_000_000;
        
        // Вставка
        long start = System.nanoTime();
        for (int i = 0; i < SIZE; i++) {
            map.put(i, "value" + i);
        }
        long insertTime = System.nanoTime() - start;
        
        // Поиск (случайные ключи)
        Random rand = new Random();
        start = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            map.get(rand.nextInt(SIZE));
        }
        long searchTime = System.nanoTime() - start;
        
        System.out.println(name + ":");
        System.out.println("  Вставка 1M элементов: " + insertTime / 1_000_000 + "ms");
        System.out.println("  Поиск 10K элементов: " + searchTime / 1_000_000 + "ms");
        System.out.println();
    }
}

/* Примерный вывод:
HashMap:
  Вставка 1M элементов: 150ms
  Поиск 10K элементов: 2ms

TreeMap:
  Вставка 1M элементов: 500ms
  Поиск 10K элементов: 5ms
*/

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

Сценарий 1: Отсортированные данные

// ✅ TreeMap отсортирована по ключам
TreeMap<Integer, String> scores = new TreeMap<>();
scores.put(100, "Alice");
scores.put(85, "Bob");
scores.put(95, "Charlie");
scores.put(75, "David");

// Итерация — уже отсортирована
for (Integer score : scores.keySet()) {
    System.out.println(score);  // 75, 85, 95, 100
}

// Или в обратном порядке
for (Integer score : scores.descendingKeySet()) {
    System.out.println(score);  // 100, 95, 85, 75
}

Сценарий 2: Операции с диапазонами

// TreeMap отлично подходит для диапазонных запросов
TreeMap<Integer, String> products = new TreeMap<>();
products.put(100, "Product A");
products.put(200, "Product B");
products.put(300, "Product C");
products.put(400, "Product D");
products.put(500, "Product E");

// Получить товары с ценой от 200 до 400
SortedMap<Integer, String> priceRange = products.subMap(200, 400);
// {200=Product B, 300=Product C}

// Товары дешевле 300
SortedMap<Integer, String> cheap = products.headMap(300);
// {100=Product A, 200=Product B}

// Товары дороже 300
SortedMap<Integer, String> expensive = products.tailMap(300);
// {300=Product C, 400=Product D, 500=Product E}

Сценарий 3: Автоматическая сортировка

// ✅ Используй TreeMap если нужна гарантированная сортировка
TreeMap<String, Integer> studentGrades = new TreeMap<>();
studentGrades.put("Zoe", 95);
studentGrades.put("Alice", 92);
studentGrades.put("Bob", 87);
studentGrades.put("Charlie", 90);

// Студенты АВТОМАТИЧЕСКИ отсортированы по имени
for (String name : studentGrades.keySet()) {
    System.out.println(name + ": " + studentGrades.get(name));
}
// Alice: 92
// Bob: 87
// Charlie: 90
// Zoe: 95

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

// ❌ TreeMap медленнее, если не нужна сортировка
TreeMap<Integer, String> map1 = new TreeMap<>();  // O(log n) для put/get

// ✅ HashMap быстрее, если не нужна сортировка
HashMap<Integer, String> map2 = new HashMap<>();  // O(1) для put/get

// Выбор зависит от требований:
// HashMap: быстро, но не отсортирована
// TreeMap: медленнее, но отсортирована и есть операции с диапазонами

Заключение

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

Треимущество TreeMap в том, что она автоматически сортирует элементы и поддерживает эффективные операции с диапазонами (subMap, headMap, tailMap). Используй TreeMap когда нужна сортировка или работа с диапазонами ключей.