Care este complexitatea temporală pentru obținerea unui element dintr-un HashMap dacă în interior se folosește un copac roșu-negru?

În Java, începând cu versiunea 8, dacă într-un bucket HashMap există prea multe coliziuni (mai mult de 8 elemente), lista din interiorul bucket-ului se transformă într-un arbore roșu-negru pentru a îmbunătăți performanța.

Complexitatea temporară pentru obținerea unui element din HashMap în acest caz se schimbă de la O(1) amortizat (când se folosește o listă legată) la O(log n), unde n este numărul de elemente din bucket-ul respectiv (adică adâncimea arborelui).

Prin urmare, utilizând un arbore roșu-negru în interiorul bucket-ului, căutarea unui element se face în O(log n).