Какая сложность операций с ключами в среднем в TreeMap

Операции с ключами в TreeMap (вставка, удаление, поиск) имеют среднюю временную сложность O(log n), так как TreeMap реализован на основе красно-черного дерева — самобалансирующегося бинарного дерева поиска.

Пример:

TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(1, "One");   // O(log n)
treeMap.get(1);          // O(log n)
treeMap.remove(1);       // O(log n)

Нюансы:

• В худшем случае (при перебалансировке) сложность остаётся O(log n).
• Для сравнения, в HashMap аналогичные операции в среднем O(1), но без гарантии порядка.
• TreeMap поддерживает ключи в отсортированном порядке (Comparator/Comparable).