Qual è la complessità temporale di ottenere un elemento da una HashMap se al suo interno viene utilizzato un albero rosso-nero?

In Java, a partire dalla versione 8, se in un bucket di HashMap ci sono troppe collisioni (più di 8 elementi), la lista all'interno del bucket viene trasformata in un albero rosso-nero per migliorare le prestazioni.

La complessità temporale per ottenere un elemento da HashMap in questo caso cambia da O(1) ammortizzato (usando una lista collegata) a O(log n), dove n è il numero di elementi nel bucket specifico (cioè la profondità dell'albero).

Pertanto, utilizzando un albero rosso-nero all'interno del bucket, la ricerca di un elemento viene eseguita in O(log n).