Pourquoi std :: map est-il implémenté comme un arbre rouge-noir?

Pourquoi est std::mapimplémenté comme un arbre rouge-noir ?

Il existe plusieurs arbres de recherche binaires équilibrés (BST). Quels ont été les compromis de conception dans le choix d'un arbre rouge-noir?

Les deux algorithmes d'arbre à équilibrage automatique les plus courants sont probablement les arbres rouge-noir et les arbres AVL . Pour équilibrer l'arbre après une insertion / mise à jour, les deux algorithmes utilisent la notion de rotations où les nœuds de l'arbre sont tournés pour effectuer le rééquilibrage.

Alors que dans les deux algorithmes, les opérations d'insertion / suppression sont O (log n), dans le cas de la rotation de rééquilibrage de l'arbre rouge-noir est une opération O (1) tandis qu'avec AVL, il s'agit d'une opération O (log n) , ce qui rend la Arbre rouge-noir plus efficace dans cet aspect de la phase de rééquilibrage et l'une des raisons possibles pour lesquelles il est plus couramment utilisé.

Les arbres rouge-noir sont utilisés dans la plupart des bibliothèques de collections, y compris les offres de Java et de Microsoft .NET Framework.

Cela dépend vraiment de l'utilisation. L'arbre AVL a généralement plus de rotations de rééquilibrage. Donc, si votre application n'a pas trop d'opérations d'insertion et de suppression, mais pèse lourdement sur la recherche, l'arborescence AVL est probablement un bon choix.

std::map utilise l'arbre rouge-noir car il obtient un compromis raisonnable entre la vitesse d'insertion / suppression de nœuds et la recherche.

Les arbres AVL ont une hauteur maximale de 1,44 logn, tandis que les arbres RB ont un maximum de 2 logn. L'insertion d'un élément dans un AVL peut impliquer un rééquilibrage à un moment de l'arborescence. Le rééquilibrage termine l'insertion. Après l'insertion d'une nouvelle feuille, la mise à jour des ancêtres de cette feuille doit être effectuée jusqu'à la racine, ou jusqu'à un point où les deux sous-arbres sont d'égale profondeur. La probabilité d'avoir à mettre à jour k nœuds est de 1/3 ^ k. Le rééquilibrage est O (1). La suppression d'un élément peut impliquer plus d'un rééquilibrage (jusqu'à la moitié de la profondeur de l'arbre).

Les arbres RB sont des arbres B d'ordre 4 représentés comme des arbres de recherche binaires. Un 4 nœuds dans l'arbre B donne deux niveaux dans le BST équivalent. Dans le pire des cas, tous les nœuds de l'arbre sont à 2 nœuds, avec une seule chaîne de 3 nœuds jusqu'à une feuille. Cette feuille sera à une distance de 2logn de la racine.

En descendant de la racine au point d'insertion, il faut changer 4 nœuds en 2 nœuds, pour s'assurer que toute insertion ne saturera pas une feuille. En revenant de l'insertion, tous ces nœuds doivent être analysés pour s'assurer qu'ils représentent correctement 4 nœuds. Cela peut également se faire en descendant dans l'arbre. Le coût global sera le même. Il n'y a pas de repas gratuit! La suppression d'un élément de l'arborescence est du même ordre.

Tous ces arbres nécessitent que les nœuds portent des informations sur la taille, le poids, la couleur, etc. Seuls les arbres Splay sont libres de ces informations supplémentaires. Mais la plupart des gens ont peur des arbres Splay, à cause de la nature aléatoire de leur structure!

Enfin, les arbres peuvent également transporter des informations sur le poids dans les nœuds, ce qui permet un équilibrage du poids. Divers schémas peuvent être appliqués. Il faut rééquilibrer lorsqu'un sous-arbre contient plus de 3 fois le nombre d'éléments de l'autre sous-arbre. Le rééquilibrage est à nouveau effectué soit par une rotation simple ou double. Cela signifie un pire cas de 2.4logn. On peut s'en tirer avec 2 fois au lieu de 3, un bien meilleur rapport, mais cela peut signifier laisser un peu moins de 1% des sous-arbres déséquilibrés ici et là. Rusé!

Quel type d'arbre est le meilleur? AVL à coup sûr. Ils sont les plus simples à coder et ont leur pire hauteur la plus proche de logn. Pour un arbre de 1000000 éléments, un AVL sera au maximum de hauteur 29, un RB 40, et un poids équilibré 36 ou 50 selon le rapport.

Il existe de nombreuses autres variables: caractère aléatoire, ratio d'ajouts, de suppressions, de recherches, etc.

Les réponses précédentes ne traitent que des alternatives d'arbres et le rouge noir ne reste probablement que pour des raisons historiques.

Pourquoi pas une table de hachage?

Un type requiert uniquement l' <opérateur (comparaison) comme clé dans une arborescence. Cependant, les tables de hachage nécessitent que chaque type de clé ait une hashfonction définie. Garder les exigences de type au minimum est très important pour la programmation générique afin que vous puissiez l'utiliser avec une grande variété de types et d'algorithmes.

Concevoir une bonne table de hachage nécessite une connaissance intime du contexte dans lequel elle sera utilisée. Doit-il utiliser l'adressage ouvert ou le chaînage lié? Quels niveaux de charge doit-il accepter avant de redimensionner? Doit-il utiliser un hachage coûteux qui évite les collisions, ou qui est rude et rapide?

Étant donné que la STL ne peut pas prévoir quel est le meilleur choix pour votre application, la valeur par défaut doit être plus flexible. Les arbres "fonctionnent" et évoluent bien.

(C ++ 11 a ajouté des tables de hachage avec unordered_map. Vous pouvez voir dans la documentation qu'il nécessite de définir des politiques pour configurer bon nombre de ces options.)

Et les autres arbres?

Les arbres rouges noirs offrent une recherche rapide et s'équilibrent automatiquement, contrairement aux BST. Un autre utilisateur a souligné ses avantages par rapport à l'arborescence AVL à équilibrage automatique.

Alexander Stepanov (le créateur de STL) a déclaré qu'il utiliserait un arbre B * au lieu d'un arbre rouge-noir s'il écrivait à std::mapnouveau, car il est plus convivial pour les caches de mémoire modernes.

L'un des plus grands changements depuis lors a été la croissance des caches. Les erreurs de cache sont très coûteuses, la localité de référence est donc beaucoup plus importante maintenant. Les structures de données basées sur des nœuds, qui ont une faible localité de référence, ont beaucoup moins de sens. Si je concevais STL aujourd'hui, j'aurais un ensemble différent de conteneurs. Par exemple, un arbre B * en mémoire est un bien meilleur choix qu'un arbre rouge-noir pour implémenter un conteneur associatif. - Alexander Stepanov

Les cartes devraient-elles toujours utiliser des arbres?

Une autre implémentation possible des cartes serait un vecteur trié (tri par insertion) et une recherche binaire. Cela fonctionnerait bien pour les conteneurs qui ne sont pas souvent modifiés mais qui sont fréquemment interrogés. Je fais souvent cela en C au fur qsortet à mesure que je suis bsearchintégré.

Dois-je même utiliser la carte?

Considérations de cache signifient il est rarement judicieux d'utiliser std::listou std::dequeplus , std:vectormême pour ces situations nous ont été enseignées à l' école (comme la suppression d' un élément du milieu de la liste). Appliquant ce même raisonnement, l'utilisation d'une boucle for pour rechercher une liste de manière linéaire est souvent plus efficace et plus propre que de créer une carte pour quelques recherches.

Bien sûr, le choix d'un conteneur lisible est généralement plus important que les performances.

Mise à jour du 14/06/2017: webbertiger modifie sa réponse après avoir commenté. Je dois souligner que sa réponse est désormais bien meilleure à mes yeux. Mais j'ai gardé ma réponse tout comme des informations complémentaires ...

En raison du fait que je pense que la première réponse est fausse (correction: plus les deux) et la troisième a une affirmation erronée. Je sens que je devais clarifier les choses ...

Les 2 arbres les plus populaires sont AVL et Red Black (RB). La principale différence réside dans l'utilisation:

• AVL: Mieux si le ratio de consultation (lecture) est supérieur à la manipulation (modification). L'empreinte mémoire est un peu inférieure à RB (en raison du peu nécessaire pour la coloration).
• RB: Mieux dans les cas généraux où il y a un équilibre entre consultation (lecture) et manipulation (modification) ou plus de modification par rapport à la consultation. Une empreinte mémoire légèrement plus grande en raison du stockage du drapeau rouge-noir.

La principale différence vient de la coloration. Vous avez moins d'action de rééquilibrage dans l'arborescence RB qu'AVL car la coloration vous permet parfois d'ignorer ou de raccourcir les actions de rééquilibrage qui ont un coût relativement élevé. En raison de la coloration, l'arbre RB a également un niveau de nœuds plus élevé car il pourrait accepter des nœuds rouges entre les noirs (ayant la possibilité de ~ 2x plus de niveaux) rendant la recherche (lecture) un peu moins efficace ... mais parce que c'est un constante (2x), elle reste en O (log n).

Si vous considérez le résultat de performance pour une modification d'un arbre (significatif) VS le résultat de performance de consultation d'un arbre (presque insignifiant), il devient naturel de préférer RB à AVL pour un cas général.

C'est juste le choix de votre implémentation - ils peuvent être implémentés comme n'importe quel arbre équilibré. Les différents choix sont tous comparables avec des différences mineures. Par conséquent, tout est aussi bon que tout.