¿Cómo se realiza la búsqueda de un elemento por clave en la estructura de datos TreeMap y cuál es la complejidad de este proceso?

В структуре данных TreeMap поиск элемента по ключу осуществляется с помощью сбалансированного бинарного дерева (обычно красно-черного дерева). Поиск начинается с корня дерева и на каждом шаге сравнивается искомый ключ с ключом текущего узла:

• Если ключ совпадает, возвращается соответствующее значение.
• Если искомый ключ меньше, поиск продолжается в левом поддереве.
• Если больше — в правом поддереве.

Так как дерево сбалансировано, высота дерева примерно равна (O(\log n)), где (n) — количество элементов. Следовательно, сложность поиска элемента по ключу в TreeMap — (O(\log n)).