Wat is de tijdcomplexiteit van het ophalen van een element uit een HashMap als er een rode-zwart boom binnenin wordt gebruikt?

In Java, vanaf versie 8, als er in een HashMap-bucket te veel botsingen zijn (meer dan 8 elementen), wordt de lijst binnen de bucket omgezet in een rood-zwart boom om de prestaties te verbeteren.

De tijdcomplexiteit voor het verkrijgen van een element uit de HashMap in dit geval verandert van geamortiseerde O(1) (bij gebruik van een gekoppelde lijst) naar O(log n), waarbij n het aantal elementen in die specifieke bucket is (d.w.z. de diepte van de boom).

Dus, bij gebruik van een rood-zwart boom binnen de bucket, wordt het zoeken naar een element uitgevoerd in O(log n).