Rouge noir arbre avl arbres

AVL Rouge et noir les arbres sont à la fois auto-équilibrage à l'exception de Rouge et de noir, couleurs des nœuds. Quelle est la raison principale pour choisir Rouge noir des arbres au lieu de AVL arbres? Quelles sont les applications de Rouge, de noir les arbres?

InformationsquelleAutor suren | 2012-12-13
  1. 89

    Quelle est la raison principale pour choisir Rouge noir des arbres au lieu de AVL arbres?

    Les deux arbres rouge-noir et AVL arbres sont les plus couramment utilisés équilibré binaires de recherche arbres, et en soutien à l'insertion, la suppression et la recherche dans la garantie O(logN) time. Cependant, il ya la suite de points de comparaison entre les deux:

    • AVL arbres sont plus rigides équilibré et donc plus rapide look-ups. Ainsi, pour une tâche fastidieuse qui consiste à utiliser un arbre AVL.
    • Pour une insertion tâches intensives, utilisez un Rouge-Noir arbre.
    • AVL arbres stockent le facteur à chaque nœud. Cela prend O(N) extra space. Cependant, si nous savons que les touches qui sera inséré dans l'arbre sera toujours plus grande que zéro, nous pouvons utiliser le bit de signe de la clés pour stocker les informations sur la couleur d'un rouge-l'arbre noir. Ainsi, dans de tels cas rouge-noir arbre O(1) extra space.
    • En général, les rotations pour un arbre AVL sont plus difficiles à mettre en œuvre et de débogage que pour un Rouge-Noir arbre.

    Ce sont l'application de la Rouge noir arbre?

    Arbres rouge-noir sont plus d'usage général. Ils font relativement bien sur ajouter, de supprimer et de recherche, mais AVL arbres ont plus rapides look-ups au prix d'une moindre ajouter/supprimer. Rouge-noir arbre est utilisé dans la suite de:

    • Java: java.util.TreeMap, java.util.TreeSet
    • C++ STL: carte, multimap, multiset
    • Noyau Linux: completely fair scheduler, linux/rbtree.h
    • In general, the rotations for an AVL tree are harder to implement and debug than that for a Red-Black tree. n'est pas vrai.
    • Pour être pédant, la norme C++ n'a pas de mandat que std:: map et ses amis utilisent aucune structure particulière. Cela est laissé à la mise en œuvre, bien que libstdc++ et Dinkumware au moins utilise des arbres rouge-noir, et il semble que vous êtes en droit dans la pratique.
    • Le facteur stockées dans chaque nœud d'un arbre AVL est de deux bits (-1 / 0 / +1). Un rouge-noir arbre stocke un peu de couleur dans chaque nœud. Ainsi, au total, les deux arbres ont besoin d'O(N) mémoire pour l'information supplémentaire.
    • "Pour une insertion tâches intensives, utilisez un Rouge-Noir l'arbre." Pourquoi? AVL arbres d'insertion suffit d'une rotation au pire, tandis que le Rouge Noir de l'arbre peut prendre deux.
    • Il est bon de savoir que dans Java 8, HashMap utilisera Rouge Noir Arbre si la linkedlist dans un seau est de plus de 8.
    • Cela devrait être mis à jour par Ben Pfaff en 2003, l'analyse de la STB performance - AVL arbres sont plus d'usage général et de mieux performer. Exact des raisons historiques pour Java, C++ et le noyau Linux et le choix le plus lent de la mise en œuvre serait intéressant de retracer.
    • Êtes-vous reportant à la section Analyse de la Performance des techniciennes se chargent du Logiciel Système? Le résumé dit: "Les résultats indiquent que lorsque l'entrée est prévu pour être commandé au hasard avec parfois des pistes de l'ordre de tri, arbres rouge-noir sont privilégiées; lorsque les insertions se produisent souvent dans l'ordre de tri, AVL arbres excel pour plus tard d'accès aléatoire, alors que les arbres s'écartent effectuer le meilleur pour plus tard, séquentielle ou le cluster d'accès". Je n'ai pas encore lu le reste du livre.
    • Il y a beaucoup de RUMEUR autour du coût de l'équilibrage AVL arbres; la vérité de la question est que ils sont presque exactement les mêmes, sauf AVL arbres décident de tourner un peu plus souvent. En conséquence, insérez-les charges de travail intensives où la commande est bien randomisés peut mettre fin au gaspillage de travail. De façon générale, je suis assez sûr AVL arbres sont encore mieux pour la plupart des cas, surtout depuis que, même dans l'insertion de lourdes charges de travail les rotations sont utiles lorsque les éléments sont déjà commandés -- et les données sont très souvent déjà commandé.

    InformationsquelleAutor Nikunj Banka
  2. 9

    Essayez de lire cette l'article

    Il propose quelques bonnes idées sur les différences, les similitudes, les performances, etc.

    Voici une citation de l'article:

    RB-Arbres sont, ainsi que AVL arbres, de auto-équilibrage. Les deux fournissent O(log n) de recherche et d'insertion de la performance.

    La différence est que RB-Arbres de garantie O(1) rotations par opération d'insertion. C'est ce qui en fait les frais réel les performances des implémentations.

    Simplifié, RB-Arbres acquérir cet avantage sur le plan conceptuel être 2-3 arbres sans avoir à transporter les frais généraux de la dynamique nœud structures. Physiquement RB-Arbres sont mis en œuvre comme des arbres binaires, le rouge/noir-drapeaux de simuler 2-3 comportement

    En ce qui concerne ma propre compréhension va, AVL arbres et RB les arbres ne sont pas très loin en termes de performances. Un RB arbre est tout simplement une variante d'un B-arbre et l'équilibrage est mis en œuvre différemment qu'un arbre AVL.

    • AFIAK, un arbre AVL est également en O(1) rotation par insertion. Pour RB arbre AVL - une insertion peut avoir 1 ou 0 rotations. Si la rotation se produit, les algorithmes d'arrêt. Si ça n'arrive pas, généralement, les algorithmes de continuer à vérifier/repeindre les nœuds du fond de la racine de l'arbre. Donc, parfois de rotation O(1) peut être mieux, car il élimine la numérisation des éléments restants O(log(n)). Parce que AVL arbres, en moyenne, fait plus de la rotation, l'arbre AVL est, en général, a un meilleur équilibre ~1.44 log(N) que RB-arbre 2 log(N).
    InformationsquelleAutor jordan
  3. 4

    Notre compréhension de la différence dans la performance s'est améliorée au fil des ans et est maintenant la raison principale de l'utilisation arbres rouge-noir plus AVL serait de ne pas avoir accès à une bonne AVL mise en œuvre, car ils sont un peu moins commun, peut-être parce qu'ils ne sont pas couverts en CLRS.

    Les deux arbres sont maintenant considérés comme des formes de rang équilibrée des arbres mais les arbres rouge-noir sont constamment plus lent par environ 20% dans le monde réel les tests. Ou même 30 à 40% plus lent lorsque les données séquentielles est inséré.

    Donc, les gens qui ont étudié les arbres rouge-noir mais pas AVL arbres ont tendance à choisir des arbres rouge-noir. Les utilisations principales pour les arbres rouge-noir sont détaillées sur le L'entrée de Wikipedia pour eux.

    • Drôle! dans ma lecture, le libavl l'article semble dire que AVL et RB sont en tête-à-tête, et ce n'est très clairement meilleur que les autres en général (ce qui est mieux dépend de la charge de travail). Je ne vois nulle part une revendication qui AVL est environ 20% plus vite.
    InformationsquelleAutor David McManamon
  4. 1

    Programmeurs n'aiment pas allouer dynamiquement de la mémoire.
    Le problème avec l'avl est un arbre que pour le "n" éléments dont vous avez besoin au moins log2(log2(n))...(hauteur->log2(n)) bits pour stocker la hauteur de l'arbre!
    Ainsi, lorsque vous manipulez énorme de données, vous ne savez pas de combien de bits à attribuer pour le stockage de hauteur à chaque nœud.

    Par exemple, si vous utilisez 4 octets int (32 bits) pour le stockage de hauteur. La hauteur maximale peut être : 2^32, et donc nombre Maximal d'éléments que vous pouvez stocker dans l'arborescence de la 2^(2^32) --(semble être très grande, mais dans cet âge de données, rien n'est trop grand, je suppose). Et donc si vous avez plus de tirer de cette limite, vous devez allouer dynamiquement de plus d'espace pour le stockage en hauteur.

    C'est une réponse proposée par un professeur de mon université qui semble raisonnable pour moi!
    Espère que je sens.

    Modifications:L'AVL arbres sont plus équilibrée par rapport à Rouge Noir des Arbres, mais ils peuvent causer plus de rotations au cours de l'insertion et de suppression. Donc, si votre application comporte de nombreuses fréquentes des insertions et des suppressions, puis Rouge Noir, les arbres doivent être privilégiées. Et si les insertions et les suppressions sont de moins en moins fréquentes et de la recherche est de plus en plus fréquentes de l'opération, puis AVL arbres doivent être préférés Rouge Noir de l'Arbre. --Source GEEKSFORGEEKS.ORG

    • Je dirais que c'est intéressant, mais peu pratique. Même s'il est vrai que, dans la plupart des compacts cas, il serait une tâche difficile de choisir le plus efficace nombre de bits à allouer à la hauteur, dans la pratique, tout à gauche de l'espace de moins d'un octet certainement inutilisée, et tout ce qui reste dans un 4 ou même 8 octets d'espace presque certainement sont inutilisées. La mémoire n'est pas alloué non alignés pour des raisons de performances considérablement la substitution de la prestation de récupérer une quantité minuscule de l'espace. Les pointeurs pour les enfants et la valeur occuper de 24 octets; 8 plus sont peu susceptibles d'avoir une pratique de coût.
    • you need need atleast log2(log2(n))...(height->log2(n)) bits to store the height of [an AVL] tree Je n'ai pas besoin de la hauteur d'un nœud dans un AVL-arbre pour le mettre en œuvre. Vous nee un peu de l'information supplémentaire pour chaque nœud (je SUIS LE PLUS grand (le frère avec la plus grande sous-arbre))); c'est plus pratique ainsi que des classiques à avoir deux des bits supplémentaires (l'enfant est plus élevé pour la gauche&droite), présenté par Un-V & L.
    • 2^(2^32) des éléments est beaucoup... comme vous pouvez stocker chaque molécule dans l'univers entier, et chaque paire possible de ces molécules, et de tous les possibles triple, et même pas encore commencer à venir, même de loin, à être à l'intérieur d'une minuscule fraction d'un tout petit pourcentage des cubes de racine de ce nombre divisé par une centaine de quintillion.
    • C'est très trompeur. Tout d'abord, nous n'avons pas besoin de stocker la hauteur dans un nœud d'un arbre AVL. Deuxièmement, même si nous l'avons fait, et même si typique de la quantité de mémoire disponible double chaque année, nous avons encore 4 milliards d'années jusqu'à la hauteur de nos arbres dépassent ce qui peut être stockée en 32 bits.
    • 2^(2^32) des objets est ridulously, follement, absolument plus que n'importe quel ordinateur, nous pouvons envisager dès maintenant retenir. Nous sommes à quelque chose comme 2^40. Vérifiez que vous êtes en mathématiques à nouveau.
    InformationsquelleAutor Prakhar Agrawal
  5. 1

    D'autres réponses ici résumer les avantages & inconvénients de la RB et AVL arbres bien, mais j'ai trouvé cette différence particulièrement intéressant:

    AVL arbres ne prennent pas en charge constante amorti de mise à jour des coûts [mais les arbres rouge-noir n']

    Source: Mehlhorn & Sanders (2008) (section 7.4)

    Ainsi, alors que les deux RB et AVL arbres garantie de O(log(N)) le pire des cas, le temps de recherche, d'insertion et de suppression, de la restauration de l'AVL/RB de la propriété après l'insertion ou la suppression d'un nœud peut être fait en O(1) amorti temps pour les arbres rouge-noir.

    • Je crois, AVL arbres d'insertion a le même coût amorti, mais produit à un meilleur équilibre de l'arbre (1.44 log(N) vs 2log(N)). Dans le même temps, la suppression AVL arbres peuvent nécessiter plus de rotations. À mon humble avis, cette question est traitée dans WAVL en.wikipedia.org/wiki/WAVL_tree
    InformationsquelleAutor emanek
  6. -1

    Ré-équilibrage de l'arbre AVL devrait rencontrer le dessous de la propriété. (Wiki De Référence - Arbre AVL)

    Dans un arbre AVL, les hauteurs des deux enfants sous-arbres d'un nœud diffèrent par un seul; si, à tout moment, ils diffèrent par plus d'un, le rééquilibrage est fait pour restaurer cette propriété.

    Donc, cela implique que la hauteur totale de l'arbre AVL ne peut pas aller fou je.e les recherches vont être mieux avec AVL Arbres. Et puisque d'autres opérations(rotations) doivent être faits pour ne pas laisser la hauteur de fous, la modification de l'arbre opérations peuvent être peu coûteux.

    • Il est mentionné dans de nombreux autres endroits, mais la raison de cette réponse n'est pas très bonne, c'est que AVL arbres et RB arbres maintenir efficacement extrêmement contraintes similaires -- RB les arbres ne seront pas plus de 2,0 fois la hauteur souhaitée, et pour les arbres AVL ce facteur est d'environ 1.44. AVL arbres tourner un peu plus souvent comme une conséquence, mais le coût par rotation est essentiellement le même; il n'est pas coûteux.
    InformationsquelleAutor samshers