На какой структуре данных основана реализация TreeMap в Java?

Красно-черное дерево (Red-Black Tree) — самобалансирующееся бинарное дерево поиска.

Основные свойства, обеспечивающие балансировку (O(log n) для put/get/remove):

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

Пример использования:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "Three");
map.put(1, "One");
map.put(2, "Two");
// Элементы автоматически сортируются по ключу (естественный порядок)
System.out.println(map); // {1=One, 2=Two, 3=Three}
// Навигационные методы
Integer lowerKey = map.lowerKey(2); // 1
Integer higherKey = map.higherKey(2); // 3

Ключи должны быть сравнимы (реализовывать Comparable) или в конструктор необходимо передать Comparator.