Как происходит вставка элемента в TreeMap

Вставка элемента в TreeMap происходит с использованием красно-чёрного дерева для поддержания сбалансированности. Процесс включает:

1. Поиск позиции: Элемент сравнивается с корневым узлом, затем рекурсивно с левыми/правыми потомками, пока не найдётся место для вставки.
2. Добавление узла: Новый элемент добавляется как лист с красным цветом (для минимизации нарушений свойств красно-чёрного дерева).
3. Балансировка: Если нарушены свойства (два красных узла подряд), выполняется перекрашивание и/или поворот дерева.

Пример:

TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "Three"); // Вставка элемента
treeMap.put(1, "One");   // Автоматическая балансировка

Сложность: O(log n) из-за сбалансированности структуры.