Почему при получении entrySet у TreeMap элементы оказываются отсортированы?

Как TreeMap обеспечивает сортировку

TreeMap — это реализация интерфейса NavigableMap, которая хранит ключи в отсортированном порядке. В основе TreeMap лежит красно-черное дерево — самобалансирующееся бинарное дерево поиска. Каждый узел дерева содержит ключ, значение, ссылки на левого и правого потомка, а также цвет (красный или черный).

Процесс вставки и сортировки

При добавлении новой пары ключ-значение TreeMap использует метод compareTo() (если ключ реализует Comparable) или compare() переданного компаратора, чтобы определить место нового узла в дереве. Узлы с меньшими ключами помещаются в левое поддерево, с большими — в правое. После вставки дерево балансируется, чтобы гарантировать логарифмическую сложность операций.

Пример кода

import java.util.*;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(3, "three");
        map.put(1, "one");
        map.put(2, "two");
        
        // entrySet() возвращает отсортированные по ключу элементы
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
        // Вывод: 1 -> one, 2 -> two, 3 -> three
    }
}

Итерация по entrySet()

Метод entrySet() возвращает Set<Map.Entry<K,V>>, который поддерживает порядок элементов согласно итератору TreeMap. Итератор выполняет обход дерева в порядке возрастания ключей (in-order traversal): сначала левое поддерево, затем корень, затем правое поддерево. Это гарантирует, что элементы будут получены в отсортированном виде.

Вывод

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