std::map std::set et autres arbres équilibrés

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 ?

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.

Salut,

Citation:

---

Envoyé par JolyLoic

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:

Citation:

---

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

---

Citation:

---

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.

---