Какова сложность алгоритма вставки (put) в TreeMap?

В Java класс TreeMap реализован на основе красно-чёрного дерева — сбалансированного бинарного дерева поиска.

Сложность операции вставки (put) в TreeMap составляет O(log n), где n — количество элементов в карте.

Это связано с тем, что для вставки нужно:

• Найти позицию для нового ключа (поиск в дереве) — O(log n).
• Вставить элемент и при необходимости выполнить балансировку дерева (повороты и перекраску) — тоже O(log n) в худшем случае.

Таким образом, вставка в TreeMap эффективна и масштабируема благодаря сбалансированной структуре данных.