Discussion :

[acx01b]

Bonjour,

À chaque fois je me pose la question :
map et set sont implémentés "a priori" avec des arbres binaires, mais sont-ils équilibrés à chaque insertion/suppression ?

Où est-ce qu'on peut voir la liste des structures de données implémentées dans les diverses versions de la STL ?

[JolyLoic]

La seule chose spécifiée, c'est la complexité. Maintenant, celle-ci implique une structure sous-jacente et ne laisse pas tant de choix. L'arbre doit être relativement équilibré, même dans les scénarios "worst-case". Globalement, ça laisse les arbres AVL et Red-Black

En pratique, toutes les implémentations que je connais sont basées sur du Red-Black. Je ne sais pas pour quelle raison.

[bertry]

Salut,

En pratique, toutes les implémentations que je connais sont basées sur du Red-Black. Je ne sais pas pour quelle raison.

D'après Red-balck tree sur wikipedia:

Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time.

The AVL tree is another structure supporting O(log n) search, insertion, and removal. It is more rigidly balanced than red–black trees, leading to slower insertion and removal but faster retrieval.