Происходит ли сортировка в TreeMap по ключу

Происходит ли сортировка в TreeMap по ключу?

Да, TreeMap всегда сортирует элементы по ключу. Это её главное отличие от HashMap. Всё основано на красно-чёрном дереве (Red-Black Tree).

Основная характеристика TreeMap

// HashMap — БЕЗ сортировки
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("zebra", 3);
hashMap.put("apple", 1);
hashMap.put("banana", 2);

for (String key : hashMap.keySet()) {
    System.out.println(key);
}
// Вывод: zebra, apple, banana (случайный порядок)

// TreeMap — СОРТИРУЕТ по ключам
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("zebra", 3);
treeMap.put("apple", 1);
treeMap.put("banana", 2);

for (String key : treeMap.keySet()) {
    System.out.println(key);
}
// Вывод: apple, banana, zebra (ОТСОРТИРОВАНО!)

Как работает сортировка

1. По умолчанию: Natural Order (Comparable)

TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Charlie", 30);
treeMap.put("Alice", 25);
treeMap.put("Bob", 28);

for (String key : treeMap.keySet()) {
    System.out.println(key);  // Alice, Bob, Charlie
}

Строки сортируются лексикографически (как в словаре):

• "Alice" < "Bob" < "Charlie" (по букве A < B < C)

TreeMap<Integer, String> numbers = new TreeMap<>();
numbers.put(5, "five");
numbers.put(2, "two");
numbers.put(8, "eight");
numbers.put(1, "one");

for (Integer key : numbers.keySet()) {
    System.out.println(key);  // 1, 2, 5, 8 (по возрастанию)
}

2. Пользовательская сортировка: Comparator

// Сортировка по убыванию
TreeMap<Integer, String> descending = new TreeMap<>(
    (a, b) -> b.compareTo(a)  // Reverse order
);

descending.put(5, "five");
descending.put(2, "two");
descending.put(8, "eight");

for (Integer key : descending.keySet()) {
    System.out.println(key);  // 8, 5, 2 (по убыванию!)
}

// Сортировка по длине строки
TreeMap<String, Integer> byLength = new TreeMap<>(
    (s1, s2) -> {
        int cmp = Integer.compare(s1.length(), s2.length());
        if (cmp == 0) {
            return s1.compareTo(s2);  // Если длина одинакова
        }
        return cmp;
    }
);

byLength.put("apple", 1);      // длина 5
byLength.put("go", 2);         // длина 2
byLength.put("programming", 3); // длина 11

for (String key : byLength.keySet()) {
    System.out.println(key);  // go, apple, programming
}

Внутренняя структура: Red-Black Tree

TreeMap использует красно-чёрное дерево:

Этапы вставки: put(5), put(3), put(7), put(1), put(9)

                    5 (root, black)
                   / \
                 3     7
               / \   / \
              1   4 6   9

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

Это гарантирует:
✅ Сбалансированное дерево
✅ Поиск O(log n)
✅ Вставка O(log n)
✅ Удаление O(log n)

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

Вывод: TreeMap медленнее в поиске, но гарантирует порядок.

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

Пример 1: Отсортированный лидерборд

NavigableMap<Integer, List<String>> leaderboard = new TreeMap<>(
    (a, b) -> b.compareTo(a)  // По убыванию score
);

leaderboard.put(100, Arrays.asList("Alice", "Bob"));
leaderboard.put(95, Arrays.asList("Charlie"));
leaderboard.put(88, Arrays.asList("David"));

// Вывод топ 3
int rank = 1;
for (Map.Entry<Integer, List<String>> entry : leaderboard.entrySet()) {
    System.out.println(rank + ". Score: " + entry.getKey() + ": " + entry.getValue());
    rank++;
    if (rank > 3) break;
}
// Output:
// 1. Score: 100: [Alice, Bob]
// 2. Score: 95: [Charlie]
// 3. Score: 88: [David]

Пример 2: Интервалы (Range Queries)

NavigableMap<Integer, String> events = new TreeMap<>();
events.put(10, "Event A");
events.put(20, "Event B");
events.put(30, "Event C");
events.put(40, "Event D");
events.put(50, "Event E");

// Получить все события между 20 и 40
NavigableMap<Integer, String> range = events.subMap(20, true, 40, true);
for (Map.Entry<Integer, String> entry : range.entrySet()) {
    System.out.println(entry);  // 20=Event B, 30=Event C, 40=Event D
}

// Получить события до 30
NavigableMap<Integer, String> before = events.headMap(30, true);
for (Map.Entry<Integer, String> entry : before.entrySet()) {
    System.out.println(entry);  // 10=Event A, 20=Event B, 30=Event C
}

// Получить события после 30
NavigableMap<Integer, String> after = events.tailMap(30, false);
for (Map.Entry<Integer, String> entry : after.entrySet()) {
    System.out.println(entry);  // 40=Event D, 50=Event E
}

// Первый элемент
Map.Entry<Integer, String> first = events.firstEntry();
System.out.println(first);  // 10=Event A

// Последний элемент
Map.Entry<Integer, String> last = events.lastEntry();
System.out.println(last);   // 50=Event E

// Меньший элемент (ceiling)
Map.Entry<Integer, String> ceiling = events.ceilingEntry(25);
System.out.println(ceiling);  // 30=Event C (первый >= 25)

// Больший элемент (floor)
Map.Entry<Integer, String> floor = events.floorEntry(25);
System.out.println(floor);  // 20=Event B (последний <= 25)

Пример 3: Собственный Comparator для объектов

public class Student {
    private String name;
    private int gpa;  // Grade Point Average

    public Student(String name, int gpa) {
        this.name = name;
        this.gpa = gpa;
    }

    public String getName() { return name; }
    public int getGpa() { return gpa; }

    @Override
    public String toString() {
        return name + " (GPA: " + gpa + ")";
    }
}

// Сортировка студентов по GPA
TreeMap<Student, String> students = new TreeMap<>(
    (s1, s2) -> {
        // По убыванию GPA
        int cmp = Integer.compare(s2.getGpa(), s1.getGpa());
        if (cmp == 0) {
            return s1.getName().compareTo(s2.getName());  // Если GPA одинаков
        }
        return cmp;
    }
);

students.put(new Student("Alice", 95), "Engineering");
students.put(new Student("Bob", 88), "Engineering");
students.put(new Student("Charlie", 95), "Science");

for (Map.Entry<Student, String> entry : students.entrySet()) {
    System.out.println(entry.getKey() + " - " + entry.getValue());
}
// Output:
// Alice (GPA: 95) - Engineering
// Charlie (GPA: 95) - Science
// Bob (GPA: 88) - Engineering

Пример 4: Временные события (Timeline)

import java.time.LocalDateTime;

NavigableMap<LocalDateTime, String> timeline = new TreeMap<>();
timeline.put(LocalDateTime.of(2024, 1, 15, 9, 30), "Meeting with client");
timeline.put(LocalDateTime.of(2024, 1, 10, 14, 0), "Code review");
timeline.put(LocalDateTime.of(2024, 1, 20, 16, 45), "Deployment");
timeline.put(LocalDateTime.of(2024, 1, 5, 10, 15), "Project kickoff");

// Все события отсортированы по времени
for (Map.Entry<LocalDateTime, String> entry : timeline.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}
// Output:
// 2024-01-05T10:15: Project kickoff
// 2024-01-10T14:00: Code review
// 2024-01-15T09:30: Meeting with client
// 2024-01-20T16:45: Deployment

// События за период
LocalDateTime start = LocalDateTime.of(2024, 1, 10, 0, 0);
LocalDateTime end = LocalDateTime.of(2024, 1, 18, 0, 0);

NavigableMap<LocalDateTime, String> period = timeline.subMap(start, end);
for (Map.Entry<LocalDateTime, String> entry : period.entrySet()) {
    System.out.println(entry.getValue());
}
// Output:
// Code review
// Meeting with client

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

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

• Нужна отсортированная коллекция по ключам
• Нужны range queries (между значениями)
• Нужны first/last элементы
• Нужна NavigableMap функциональность
• Нужна предсказуемость порядка

❌ НЕ используй TreeMap когда:

• Нужна максимальная скорость (используй HashMap)
• Не важен порядок элементов (используй HashMap)
• Нужен insertion order (используй LinkedHashMap)
• Много операций поиска (HashMap быстрее)

Сравнение трёх map'ов

Map<String, Integer> data = new LinkedHashMap<>();
data.put("zebra", 1);
data.put("apple", 2);
data.put("banana", 3);

// HashMap
Map<String, Integer> hashMap = new HashMap<>(data);
for (String key : hashMap.keySet()) {
    System.out.println(key);  // apple, zebra, banana (случайный)
}

// TreeMap
Map<String, Integer> treeMap = new TreeMap<>(data);
for (String key : treeMap.keySet()) {
    System.out.println(key);  // apple, banana, zebra (ОТСОРТИРОВАНО)
}

// LinkedHashMap
Map<String, Integer> linkedHashMap = new LinkedHashMap<>(data);
for (String key : linkedHashMap.keySet()) {
    System.out.println(key);  // zebra, apple, banana (insertion order)
}

Итоговый вывод

TreeMap — это отсортированная Map, основанная на красно-чёрном дереве.

Ключевые моменты:

1. Всегда сортирует по ключам (естественный или пользовательский порядок)
2. Сложность O(log n) для основных операций
3. NavigableMap методы (subMap, headMap, tailMap, ceiling, floor)
4. Red-Black Tree гарантирует баланс
5. Медленнее HashMap, но с гарантированным порядком

Треди для данных, где порядок важен: рейтинги, временные шкалы, интервалы!