Quelle est la complexité temporelle pour obtenir un élément d'une HashMap si elle utilise un arbre rouge-noir à l'intérieur?

Dans Java, à partir de la version 8, si un bucket de HashMap a trop de collisions (plus de 8 éléments), la liste à l'intérieur du bucket est transformée en un arbre rouge-noir pour améliorer les performances.

La complexité temporelle pour obtenir un élément de HashMap dans ce cas passe de O(1) amorti (lorsqu'on utilise une liste chaînée) à O(log n), où n est le nombre d'éléments dans ce bucket (c'est-à-dire la profondeur de l'arbre).

Ainsi, en utilisant un arbre rouge-noir à l'intérieur du bucket, la recherche d'un élément s'effectue en O(log n).