Какая структура данных лежит в основе TreeMap

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

Ключевые особенности:

• Каждый узел содержит цвет (красный или черный)
• Корень всегда черный
• Все листья (NIL) считаются черными
• Красный узел не может иметь красных потомков
• Все пути от узла до листьев содержат одинаковое количество черных узлов

Пример создания TreeMap:

TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "Three");
treeMap.put(1, "One");
treeMap.put(2, "Two");
// Элементы автоматически сортируются по ключу