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

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

Это связано с тем, что TreeMap основан на структуре данных "красно-черное дерево". В таком дереве, балансировка гарантирует, что высота дерева логарифмически зависит от количества узлов. Операции поиска, вставки и удаления требуют обхода дерева от корня до нужного узла, что занимает время, пропорциональное высоте дерева.

// Пример поиска в TreeMap
import java.util.TreeMap;

public class TreeMapSearch {

    public static void main(String[] args) {
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(5, "Пять");
        treeMap.put(2, "Два");
        treeMap.put(8, "Восемь");
        treeMap.put(1, "Один");
        treeMap.put(6, "Шесть");

        // Поиск элемента с ключом 8
        String value = treeMap.get(8);
        // Сложность этой операции O(log n)
        System.out.println("Значение по ключу 8: " + value);

        // Поиск элемента с несуществующим ключом 10
        String notFoundValue = treeMap.get(10);
        // Сложность этой операции тоже O(log n)
        System.out.println("Значение по ключу 10: " + notFoundValue);
    }
}