Qual algoritmo é utilizado para procurar um elemento no TreeMap e quão eficiente é?

O TreeMap em Java é implementado com base numa árvore vermelho-preto, que é uma variedade de árvore binária de pesquisa balanceada. Para procurar um elemento, é utilizado um algoritmo de busca binária na árvore, que, devido ao balanceamento, mantém a altura da árvore aproximadamente igual a (O(\log n)).

Isto garante uma pesquisa, inserção e remoção eficientes em tempo (O(\log n)), muito mais rápido do que a busca linear numa estrutura não ordenada.

Exemplo de uso do TreeMap:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "dez");
map.put(5, "cinco");
map.put(20, "vinte");

String value = map.get(10); // busca pela chave 10 em O(log n)