Какую структуру данных имплементирует TreeMap

TreeMap в Java реализует интерфейс NavigableMap, который расширяет SortedMap. В основе лежит красно-черное дерево (Red-Black Tree) — самобалансирующееся бинарное дерево поиска. Это гарантирует логарифмическое время O(log n) для операций put, get, remove и containsKey.

Пример:

TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "Three");
treeMap.put(1, "One");
treeMap.put(2, "Two");

System.out.println(treeMap); // {1=One, 2=Two, 3=Three} (автоматическая сортировка)

Особенности:

• Элементы хранятся в отсортированном порядке (по ключам).
• Поддерживает методы для работы с порядком (firstKey(), lastKey(), headMap(), tailMap()).
• Не допускает null-ключи (если используется natural ordering).