В чем разница между TreeSet и TreeMap?

# Разница между TreeSet и TreeMap

Краткий ответ

TreeSet - это отсортированное множество (Set), которое хранит уникальные элементы в порядке сортировки. TreeMap - это отсортированная таблица (Map), которая хранит пары ключ-значение в порядке сортировки ключей.

Оба основаны на Red-Black дереве и имеют аналогичные операции, но работают с разными структурами данных.

1. TreeSet

Интерфейс: Set<E> (множество)

Структура данных: Red-Black дерево

Хранит: Уникальные элементы в отсортированном порядке

TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(2);
numbers.add(8);
numbers.add(1);

System.out.println(numbers);  // [1, 2, 5, 8] - автоматически отсортировано

// Методы Set
numbers.contains(2);           // true
numbers.remove(5);             // true
numbers.size();                // 3

// Методы NavigableSet (полезные)
numbers.first();               // 1
numbers.last();                // 8
numbers.ceiling(6);            // 8 (первый >= 6)
numbers.floor(6);              // 5 (первый <= 6)
numbers.lower(6);              // 5 (первый < 6)
numbers.higher(6);             // 8 (первый > 6)
numbers.headSet(6);            // [1, 2, 5]
numbers.tailSet(6);            // [8]
numbers.subSet(2, 8);          // [2, 5]

Характеристики:

• Все элементы уникальны
• Отсортированы в natural order
• Можно задать свой Comparator
• null не допускается
• O(log n) для add, remove, contains
• O(n) для итерацию в порядке сортировки

2. TreeMap

Интерфейс: Map<K, V> (словарь)

Структура данных: Red-Black дерево

Хранит: Пары ключ-значение, отсортированные по ключам

TreeMap<String, Integer> scores = new TreeMap<>();
scores.put("Alice", 95);
scores.put("Charlie", 88);
scores.put("Bob", 92);

System.out.println(scores);
// {Alice=95, Bob=92, Charlie=88} - отсортировано по ключам

// Методы Map
scores.get("Bob");             // 92
scores.containsKey("Alice");   // true
scores.remove("Charlie");      // 88
scores.size();                 // 2

// Методы NavigableMap (полезные)
scores.firstKey();             // "Alice"
scores.lastKey();              // "Bob"
scores.ceilingKey("B");        // "Bob" (первый >= "B")
scores.floorKey("B");          // "Alice" (первый <= "B")
scores.lowerKey("B");          // "Alice" (первый < "B")
scores.higherKey("B");         // "Bob" (первый > "B")
scores.headMap("C");           // {Alice=95, Bob=92}
scores.tailMap("B");           // {Bob=92}
scores.subMap("A", "C");       // {Alice=95, Bob=92}

// Итерация в порядке ключей
for (String name : scores.keySet()) {
    System.out.println(name + ": " + scores.get(name));
}

Характеристики:

• Все ключи уникальны
• Отсортированы по ключам
• null ключи не допускаются (может быть null-значение)
• O(log n) для put, get, remove
• O(n) для итерацию в порядке ключей

3. Сравнение

4. Внутренняя структура

TreeSet - использует TreeMap

public class TreeSet<E> {
    private transient NavigableMap<E, Object> m;  // внутри использует TreeMap!
    
    public TreeSet() {
        this.m = new TreeMap<>();
    }
    
    public boolean add(E e) {
        return m.put(e, PRESENT) == null;  // элемент как ключ, значение - dummy
    }
}

Таким образом, TreeSet фактически использует TreeMap с фиксированным значением!

5. Практические примеры

TreeSet

// Отсортированный список уникальных ID
TreeSet<String> uniqueIds = new TreeSet<>();
uniqueIds.add("ID-5");
uniqueIds.add("ID-2");
uniqueIds.add("ID-8");
// Автоматически отсортировано

// Найти все ID в диапазоне
Set<String> range = uniqueIds.subSet("ID-3", "ID-7");  // [ID-5]

// Медиана
TreeSet<Integer> scores = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50));
Integer median = scores.floor((scores.first() + scores.last()) / 2);

TreeMap

// Словарь с отсортированными ключами (например, по дате)
TreeMap<LocalDate, Double> stockPrices = new TreeMap<>();
stockPrices.put(LocalDate.of(2024, 1, 1), 100.0);
stockPrices.put(LocalDate.of(2024, 1, 5), 102.0);
stockPrices.put(LocalDate.of(2024, 1, 3), 101.0);

// Получить цены между датами
NavigableMap<LocalDate, Double> range = 
    stockPrices.subMap(
        LocalDate.of(2024, 1, 2), 
        LocalDate.of(2024, 1, 5)
    );

// Самая высокая цена
Double maxPrice = stockPrices.lastEntry().getValue();

// История цен в порядке дат
for (Map.Entry<LocalDate, Double> entry : stockPrices.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

6. Сложность операций

Обе структуры используют Red-Black дерево

Операция      | TreeSet | TreeMap
-----------   | ------- | -------
add/put       | O(log n)| O(log n)
remove        | O(log n)| O(log n)
contains/Get  | O(log n)| O(log n)
first/last    | O(1)    | O(1)
headSet/Map   | O(log n)| O(log n)
tailSet/Map   | O(log n)| O(log n)
subSet/Map    | O(log n)| O(log n)

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

TreeSet

• Нужен отсортированный список уникальных элементов
• Нужно быстро найти элемент в диапазоне
• Нужна итерация в отсортированном порядке
• Например: список уникальных ID, рейтинги, очереди приоритетов

TreeMap

• Нужен словарь с отсортированными ключами
• Нужно быстро найти ключ в диапазоне
• Нужна итерация по ключам в отсортированном порядке
• Например: кэш с датами, таблица с отсортированными ID, история событий

8. Пример: Range query

// TreeSet - найти все числа между 5 и 10
TreeSet<Integer> numbers = new TreeSet<>(Arrays.asList(1, 3, 5, 7, 9, 11, 13));
NavigableSet<Integer> range = numbers.subSet(5, 10);  // [5, 7, 9]

// TreeMap - найти все записи за период
TreeMap<LocalDate, String> events = new TreeMap<>();
events.put(LocalDate.of(2024, 1, 1), "Event A");
events.put(LocalDate.of(2024, 1, 15), "Event B");
events.put(LocalDate.of(2024, 2, 1), "Event C");

NavigableMap<LocalDate, String> januaryEvents = 
    events.subMap(
        LocalDate.of(2024, 1, 1), 
        LocalDate.of(2024, 2, 1)
    );

Заключение

• TreeSet - отсортированное множество для хранения уникальных элементов
• TreeMap - отсортированный словарь для хранения пар ключ-значение
• Оба основаны на Red-Black дереве
• Обе обеспечивают O(log n) операции
• TreeSet фактически использует TreeMap изнутри
• Выбирайте TreeSet для элементов, TreeMap для пар ключ-значение