Qual é a complexidade do algoritmo de inserção (put) no TreeMap?

Em Java, a classe TreeMap é implementada com base numa árvore vermelho-preto, uma árvore binária de pesquisa balanceada.

A complexidade da operação de inserção (put) no TreeMap é O(log n), onde n é o número de elementos no mapa.

Isto deve-se ao facto de que, para inserir, é necessário:

• Encontrar a posição para a nova chave (pesquisa na árvore) — O(log n).
• Inserir o elemento e, se necessário, realizar o balanceamento da árvore ( rotações e re-coloração) — também O(log n) no pior caso.

Assim, a inserção no TreeMap é eficiente e escalável graças à sua estrutura de dados balanceada.