Pourquoi est std::map mis en œuvre comme un rouge-noir arbre?

Pourquoi est std::map mis en œuvre comme un rouge-noir arbre?

Il y a plusieurs équilibré arbres binaires (techniciennes se chargent) là-bas. Quelles ont été la conception de compromis dans le choix d'un rouge-noir arbre?

  • Bien que toutes les implémentations que j'ai vu utiliser un RB-tree, note que c'est encore dépendant de l'implémentation.
  • Il est dépendant de l'implémentation, alors pourquoi il en est ainsi que la mise en œuvre utilisation RB-arbres?
  • J'aimerais vraiment savoir si tout STL réalisateur a pensé à l'aide d'une benne de la Liste.
  • C++de map et set sont effectivement commandé la carte et de l'ensemble ordonné. Ils ne sont pas mis en œuvre à l'aide de fonctions de hachage. Chaque requête est prendre O(logn) et pas O(1), mais les valeurs sont toujours triés. À partir de C++11 (je crois), il y a unordered_map et unordered_set, qui sont mis en œuvre à l'aide de fonctions de hachage, et bien qu'ils ne sont pas triés, la plupart des requêtes et les opérations sont possibles dans O(1) (moyennement)
  • c'est vrai, mais pas que c'est intéressant dans la pratique. Le standard de fait de la complexité des garanties avec un algorithme spécifique ou un ensemble d'algorithmes dans l'esprit.
  • Il existe plusieurs autres types de auto-équilibrage des arbres avec le même big-O complexité rouge-noir arbre, comme le B-arbre et arbre AVL.

InformationsquelleAutor Denis Gorodetskiy | 2011-03-13
  1. 107

    Probablement les deux plus commun d'auto équilibrage de l'arbre algorithmes sont Arbres rouge-Noir et AVL arbres. À l'équilibre de l'arbre, après une insertion/mise à jour deux algorithmes utilisent la notion de rotations où les nœuds de l'arbre sont en rotation pour effectuer le ré-équilibrage.

    Alors que dans les deux algorithmes d'insérer ou de supprimer des opérations sont en O(log n), dans le cas de la Rouge-Noir arbre de ré-équilibrage de la rotation est un O(1) opération alors qu'avec AVL c'est un O(log n) opération, ce qui rend le Rouge-Noir arbre plus efficace dans cet aspect de la ré-équilibrage de la scène et l'une des raisons pour lesquelles il est plus couramment utilisé.

    Arbres rouge-Noir sont utilisés dans la plupart de la collection de bibliothèques, y compris les offres de Java et Microsoft .NET Framework.

    • vous faire sonner comme des arbres rouge-noir peut faire l'arbre des modifications en O(1) le temps, ce qui n'est pas vrai. arbre des modifications sont en O(log n) pour les deux rouge-noir et AVL arbres. qui rend discutable si l'équilibrage de la partie de la modification de l'arbre est O(1) O(log n) en raison de l'opération principale est déjà en O(log n). après tout, même le peu de travail supplémentaire que AVL arbres ne résulte une plus étroitement équilibré arbre qui conduit à des recherches légèrement plus rapide. donc c'est un bon compromis et ne pas faire AVL arbres inférieurs aux arbres rouge-noir.
    • mehx, je suis en référence à la rotation de la partie de l'algorithme. Je vais mettre à jour pour être plus clair.
    • donc, voir ma réponse ci-dessous.
    • Vous devez regarder au-delà de la complexité réelle de l'exécution de voir une différence - AVL arbres ont généralement une plus faible total d'exécution quand il ya beaucoup plus de recherches que les insertions/suppressions. RB arbres ont une plus faible total d'exécution quand il ya beaucoup plus d'insertions/suppressions. La proportion exacte à laquelle la rupture se produit dépend bien sur de nombreux détails de la mise en œuvre, de matériel et d'utilisation précises, mais depuis la bibliothèque d'auteurs ont en charge d'une vaste gamme de modèles d'utilisation, ils ont à prendre une supposition éclairée. AVL est également un peu plus difficile à mettre en œuvre, de sorte que vous voudrez peut-être un bienfait prouvé à l'utiliser.
    • Alors, pourquoi la décision a été prise pour rendre RB arborescence par défaut impl? Voulez-vous dire qu'il y a plus d'insertions/suppressions de recherches en général?
    • RB arbre n'est pas un "défaut de mise en œuvre". Chaque opérateur choisit une mise en œuvre. Aussi loin que nous le savons, ils ont tous choisi RB arbres, de sorte que sans doute c'est soit pour la performance ou pour la facilité de mise en oeuvre/maintenance. Comme je l'ai dit, le point d'arrêt pour la performance pourrait ne pas sous-entendre qu'il pense qu'il y a plus d'insertions/suppressions de recherches, c'est juste que le rapport entre les deux est au-dessus du niveau où ils pensent RB probablement beats AVL.
    • J'aimerais marquer votre commentaire une réponse si il serait pris en charge par les nombres
    • malheureusement, la seule façon d'obtenir des numéros est de faire une liste de std::map implémentations, traquer les développeurs, et demandez-leur quels critères qu'ils ont utilisés pour prendre la décision, de sorte que cela reste de la spéculation.
    • Ne pas AVL arbres et RB-Arbres O(1) pour rétablir l'équilibre amorti post-insertion?
    • Il n'y a pas beaucoup d'espace pour entrer dans les détails. Peut-être le lien suivant aidera pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Arbres/...
    • Je pense que ce lien pourrait être trompeuse. En moyenne, AVL arbres aussi de coût O(1) pour restructurer. Voir en.wikipedia.org/wiki/AVL_tree#Comparison_to_other_structures L'intuition est que RB-Arbres sont essentiellement de 2 à 3 Arbres, et losely parlant, AVL-hauteur de l'Arbre changements ne se propagent pas jusqu'Ω(n) nœuds ont été modifiés.
    • Tandis que je serais enclin à écrire un peu de code pour tester tout cela, il va falloir du temps pour écrire le code pour les deux et de prouver qu'ils ont raison. J'ai trouvé le suivant analyse pratique qui semble raisonnablement de son nathanbelue.blogspot.com/2013/01/...
    • Une fois qu'un nœud a été trouvé, AVL Arbres ont besoin de jusqu'à 2 rotations afin de corriger les hauteurs. C'est parce que l'insertion peut augmenter la hauteur du sous-arbre d'au plus 1. Cette augmentation peut être [1] dans le petit arbre (pas de rotation nécessaire) ou [2] dans le gros arbre (éventuellement aucune augmentation de la hauteur de post-rotation) ou [3] si les deux arbres sont de la même hauteur, puis d'insertion peut effectivement AUGMENTER la hauteur totale de l'arbre par 1. Cette augmentation est compensée par une rotation à un niveau plus élevé de nœud. c'est à dire des Cas [3] conduit à des cas [1] ou [2] qui sont fixées par une simple rotation.
    • Ce blog est une excellente ressource sur les pratiques de la performance, on pourrait s'attendre - merci! 🙂
    • Un Maximum de 2 rotations sont effectuées pour une insertion dans un arbre AVL, par opposition à log n rotations. voir le problème de la 3d ici ocw.mit.edu/courses/electrical-engineering-and-computer-science/...
    • c'est le nombre maximum de rotations, mais il est un O(log(n)) opérations en termes de coût. Pour être plus précis, c'est le coût amorti, tandis que le RB-Arbres ont une constante coût amorti ie. O(1) pour le post insérer des rotations.
    • C'est très cool d'observation! En effet, dans un rouge-noir arbre un maximum de 3 opérations peuvent être effectuées dans un arbre AVL un maximum de O(logN) les opérations qui peuvent être effectuées lors du changement de l'équilibre des facteurs de logN les nœuds dans l'arbre.
    • Veuillez lire les commentaire et pourriez-vous s'il vous plaît corriger votre réponse?. Vous êtes tout à fait tort, et votre réponse juste amener les gens à de fausses affirmations. La plupart de la mise en œuvre utilise Noir-Rouge, arbre, car dans le cas général où vous avez plus de manipulation que de la consultation (lire), rouge noir arbre est légèrement plus rapide, car il nécessite de ré-équilibrer les moins souvent. Mais lors de la consultation (lecture) se produit plus souvent que la manipulation, AVL est plus rapide car il est mieux équilibré. Les deux rééquilibrage sont dans le même ordre pour les deux, ce qui n'est pas O(1) O(log n).
    • Je pense que vous avez mal lu, je ne dis pas que le rééquilibrage est O(1), c'est l'étape de rotation qui est O(1) pour la R-B Arbre (à plus du double de la gauche ou rotation à droite requis),
    • La rotation s'effectue toujours en O(1) dans l'arbre de rééquilibrer l'action, il est inutile de mentionner qu'il n'apporte rien à la discussion. Tout ré-équilibrer besoin de O(1) et O(log(n)) la récursivité, afin de s'assurer de garder l'arbre règles valables. Vous pouvez lire l'excellent exemple: cs.auckland.ac.nz/software/AlgAnim/red_black_op.html afin de voir de quoi je parle. Comme dans AVL arbres, parfois vous devez faire une boucle vers le haut et réorganiser les branches afin de maintenir RB règles valables. La différence réside dans la coloration, le ré-équilibrage se produit environ 2x moins de AVL.
    • Absent de toutes les ce est le coût, au niveau de chaque nœud, pour stocker l'auxiliaire de l'information nécessaire pour faire la balance des décisions. Arbres rouge-Noir 1 bits pour représenter la couleur. AVL arbres ont besoin d'au moins 2 bits (pour représenter -1, 0 ou 1).

    InformationsquelleAutor Chris Taylor
  2. 42

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

    std::map utilise le Rouge-Noir arbre qu'il obtient un compromis raisonnable entre la vitesse de nœud d'insertion, la suppression et la recherche.

    • Êtes-vous sûr de cela??? Personnellement, je pense que le Rouge-Noir est un arbre ou les plus complexes, jamais simple. La seule chose, c'est dans le document Rd-l'arbre Noir, ré-équilibrage se produit moins souvent que les AVL.
    • Théoriquement, les deux R/B de l'arbre et de l'arbre AVL est de complexité O(log n) ) pour l'insertion et la suppression. Mais une grande partie du coût de fonctionnement est la rotation, ce qui est différent entre ces deux arbres. Veuillez consulter la discuss.fogcreek.com/joelonsoftware/... Citation: "l'équilibre entre un arbre AVL peut exiger de O(log n) rotations, tandis que le rouge noir de l'arbre prendra pas plus de deux rotations à mettre en équilibre (même s'il peut avoir à examiner O(log n) nœuds de décider où les rotations sont nécessaires)." Édité mes commentaires en conséquence.
    InformationsquelleAutor webbertiger
  3. 24

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

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

    Va vers le bas à partir de la racine du point d'insertion, on doit changer à 4 nœuds en 2-nœuds, pour s'assurer que l'insertion ne sera pas de saturer 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 aussi être fait en descendant dans l'arbre. Le coût global sera le même. Il n'y a pas de repas gratuit! Suppression d'un élément de l'arbre est du même ordre.

    Tous ces arbres ont besoin que les nœuds portent des informations sur la taille, le poids, la couleur, etc. Seulement Écarter les arbres sont gratuits à partir de ces informations supplémentaires. Mais la plupart des gens ont peur de s'écartent des arbres, à cause de la ramdomness de leur structure!

    Enfin, les arbres peuvent aussi transporter des informations de poids dans les nœuds, permettant des poids d'équilibrage. Différents systèmes peuvent être appliquées. On devrait 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 fait soit devant un simple ou double rotation. Cela signifie un pire cas de 2,4 logn. On peut s'en tirer avec 2 fois au lieu de 3, un bien meilleur ratio, mais cela peut signifier qu'il reste un peu moins que 1% de la sous-arbres déséquilibrés ici et là. Délicat!

    Quel type d'arbre est le meilleur? AVL pour vous. Ils sont les plus simples à code, et ont leurs pires hauteur la plus proche de logn. Pour un arbre de 1000000 éléments, un AVL sera au plus de hauteur de 29, un RB 40, et un poids équilibré 36 ou 50 selon le rapport.

    Il y a beaucoup d'autres variables: l'aléatoire, le ratio des ajouts, des suppressions, des recherches, etc.

    • La bonne réponse. Mais si AVLs sont les meilleurs, pourquoi bibliothèque standard met en œuvre std::map que RB arbre?
    • Je suis en désaccord que AVL arbres sont sans conteste le meilleur. Bien qu'ils aient une faible hauteur, ils ont besoin (au total) plus de travail à faire relabancing que rouge/noir arbres (O(log n) le rééquilibrage de travailler par rapport à O(1) amorti rééquilibrage de travail). S'écartent des arbres pourrait être beaucoup, beaucoup mieux et votre affirmation que les gens ont peur d'eux n'est pas fondé. Il n'est pas un universel "meilleur" de l'arbre d'équilibrage de régime là-bas.
    • Presque parfait réponse. Pourquoi avez-vous dit AVL est le meilleur. C'est tout simplement faux et c'est pourquoi la plupart des généraux de mise en œuvre utilise le Rouge-l'arbre Noir. Vous devez avoir un bon ratio plus élevé de lire plus de la manipulation de choisir AVL. Aussi, AVL a un peu moins de mémoire que RB.
    InformationsquelleAutor user847376
  4. 15

    Les réponses précédentes seulement l'adresse de l'arbre des solutions de rechange rouge et noir probablement ne reste que pour des raisons historiques.

    Pourquoi pas une table de hachage?

    Un type exige seulement partielle de la commande (< comparaison) pour être utilisé comme une clé dans un arbre. Cependant, les tables de hachage, il faut que chaque type de clé a un hash fonction définie. Le maintien de ces exigences de type à un minimum est très important pour la programmation générique.

    La conception d'une bonne table de hachage nécessite la connaissance intime du contexte, il lequel il sera utilisé. Devrait-il utiliser en abordant, ou lié chaînage? Quels sont les niveaux de charge doit-elle accepter avant de la redimensionner? Devrait-il utiliser un cher de hachage qui évite les collisions, ou celui qui est rude et rapide?

    Depuis le TSL ne pouvez pas anticiper ce qui est le meilleur choix pour votre application, le défaut doit être plus souple. Les arbres "fonctionne" et échelle bien.

    (C++11 a ajouter des tables de hachage avec unordered_map. Vous pouvez voir à partir de la la documentation il nécessite la définition des politiques de configurer plusieurs de ces options.)

    Quels sont les autres arbres?

    Rouge Noir arbre de l'offre de recherche rapide et sont auto-équilibrage, à la différence des techniciennes se chargent. Un autre utilisateur a souligné ses avantages par rapport à l'auto-équilibrage arbre AVL.

    Alexander Stepanov (Le créateur de la STL) a dit qu'il allait utiliser une B* * * * Arbre au lieu d'un Rouge-Noir arbre si il a écrit std::map de nouveau, parce que c'est plus convivial et moderne de la mémoire caches.

    Un des plus grands changements depuis lors, a été la croissance des caches.
    Le Cache est très coûteux, de sorte que la localité de référence est beaucoup plus
    important maintenant. Basées sur les nœuds des structures de données, qui ont une faible localité de
    de référence, beaucoup moins de sens. Si je devais concevoir STL aujourd'hui, je
    aurait un autre ensemble de conteneurs. Par exemple, une mémoire
    B*-arbre est un bien meilleur choix qu'un rouge-noir arbre de la mise en œuvre
    un conteneur associatif. - Alexander Stepanov

    Faut-il toujours utiliser un rouge noir arbre ou B* arbre?

    En d'autres occasions, Alex a déclaré que std::vector est presque toujours la meilleure liste de conteneur pour des raisons similaires. Il est rarement intéressant d'utiliser std::list ou std::deque même pour les situations qui nous a été enseigné à l'école (comme la suppression d'un élément à partir du milieu de la liste). std::vector est si rapide que les battements ces structures pour tout, mais les grandes N.

    L'application de ce raisonnement, si vous avez seulement un petit nombre d'éléments (des centaines?) à l'aide d'un std::vector et linéaire de la recherche peut être plus efficace que celle de l'arbre de la mise en œuvre de std::map. En fonction de la fréquence de l'insertion, triés std::vector combiné avec std::binary_search peut être le plus rapide choix.

    InformationsquelleAutor Justin Meiners
  5. 3

    Mise à jour 2017-06-14: webbertiger modifier sa réponse après que j'ai commenté. Je tiens à souligner que sa réponse est aujourd'hui beaucoup mieux à mes yeux. Mais j'ai gardé ma réponse juste à titre d'information supplémentaire...

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

    Les 2 plus populaires arbre AVL Rouge et Noir (RB). La principale différence se situent dans l'utilisation:

    • AVL : Mieux si le ratio de consultation (lecture) est plus grand que la manipulation (modification). Mémoire impression de pied est un peu moins de RB (en raison de l'bits requis pour la coloration).
    • RB : Mieux en général le cas où il existe un équilibre entre la consultation (lecture) et de manipulation (modification) ou plus de modification au cours de la consultation. Un peu plus de mémoire, en raison du stockage de red-black flag.

    La principale différence de la coloration. Vous avez moins de ré-équilibrer l'action en RB arbre que AVL parce que la coloration de vous permettre de vous parfois sauter ou de raccourcir ré-équilibrer les actions qui ont un parent hi coût. En raison de la coloration, RB arbre ont aussi plus de niveau de nœuds, car il pourrait accepter les noeuds rouges entre noirs (avoir les possibilités de ~2x plus de niveaux) ce qui rend la recherche (lire) un peu moins efficace... mais parce que c'est une constante (2x), il reste en O(log n).

    Si vous considérez l'impact sur les performances pour une modification d'un arbre (significatif) VS les performances de la consultation d'un arbre (presque insignifiant), il est naturel de préférer RB sur AVL pour un cas général.

    InformationsquelleAutor Eric Ouellet
  6. 2

    C'est juste le choix de votre mise en œuvre, elles pourraient être mises en œuvre comme l'équilibre de toute l'arbre. Les différents choix sont tous comparables, avec des différences mineures. Donc tout est bon à tout.

    InformationsquelleAutor necromancer