Какая сложность поиска элемента в TreeMap

Поиск элемента в TreeMap имеет временную сложность O(log n), так как реализован на основе красно-чёрного дерева (сбалансированного бинарного дерева поиска). Это гарантирует эффективность операций вставки, удаления и поиска.

Пример:

TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(1, "One");
treeMap.put(2, "Two");
treeMap.put(3, "Three");

// Поиск по ключу — O(log n)
String value = treeMap.get(2); // "Two"

Нюансы:

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