Qual é a complexidade temporal de obter um elemento de um HashMap se dentro dele for usado uma árvore vermelho-preto?

No Java, a partir da versão 8, se um balde de HashMap tiver muitas colisões (mais de 8 elementos), a lista dentro do balde é transformada em uma árvore vermelho-preto para melhorar o desempenho.

A complexidade temporal para obter um elemento do HashMap neste caso muda de O(1) amortizado (usando uma lista ligada) para O(log n), onde n é o número de elementos no balde específico (ou seja, a profundidade da árvore).

Assim, ao usar uma árvore vermelho-preto dentro do balde, a busca por um elemento é feita em O(log n).