Ответ
Ключи в TreeMap и TreeSet хранятся в структуре данных красно-черное дерево (Red-Black Tree).
Красно-черное дерево — это самобалансирующееся бинарное дерево поиска (БДП). Его свойства гарантируют, что основные операции (вставка, удаление, поиск) выполняются за O(log n) в худшем случае, предотвращая вырождение дерева в связный список.
Почему именно оно?
- Балансировка: Автоматически поддерживает сбалансированную высоту после каждой модификации.
- Гарантированная производительность: Логарифмическое время операций гарантировано контрактом
SortedMap/SortedSet.
Пример:
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "Three");
map.put(1, "One");
map.put(2, "Two");
// Ключи {1, 2, 3} хранятся и упорядочиваются в сбалансированном дереве
System.out.println(map); // {1=One, 2=Two, 3=Three}
System.out.println(map.get(2)); // Поиск за O(log n)