Arbre noir rouge sur arbre avl

109

AVL et les arbres noirs rouges sont tous deux auto-équilibrés, sauf les couleurs rouge et noire dans les nœuds. Quelle est la raison principale du choix des arbres noirs rouges au lieu des arbres AVL? Quelles sont les applications des arbres noirs rouges?

algorithm data-structures red-black-tree suren
la source
2
duplication possible de Pourquoi std :: map est-il implémenté en tant qu'arbre rouge-noir?
Lior Kogan
1
En passant, les développeurs de Rust ont choisi d'utiliser un arbre B au lieu de l'un ou l'autre pour leur carte ordonnée standard.
Tom Anderson

Réponses:

124

Quelle est la raison principale du choix des arbres noirs rouges au lieu des arbres AVL?

Les arbres rouge-noir et les arbres AVL sont les arbres de recherche binaires équilibrés les plus couramment utilisés et ils prennent en charge l'insertion, la suppression et la recherche garanties O(logN) time. Cependant, il existe les points de comparaison suivants entre les deux:

  • Les arbres AVL sont plus rigoureusement équilibrés et permettent donc des recherches plus rapides. Ainsi, pour une tâche intensive de recherche, utilisez une arborescence AVL.
  • Pour une insertion de tâches intensives, utilisez un arbre rouge-noir.
  • Les arborescences AVL stockent le facteur d'équilibre à chaque nœud. Cela prend O(N)plus de place. Cependant, si on sait que les clés qui seront insérées dans l'arbre seront toujours supérieures à zéro, on peut utiliser le bit de signe des clés pour stocker les informations de couleur d'un arbre rouge-noir. Ainsi, dans de tels cas, l'arbre rouge-noir ne prend pas d'espace supplémentaire.

Quelle est l'application de l'arbre noir rouge?

Les arbres rouge-noir sont plus polyvalents. Ils fonctionnent relativement bien pour l'ajout, la suppression et la recherche, mais les arbres AVL ont des recherches plus rapides au prix d'une ajout / suppression plus lente. L'arbre rouge-noir est utilisé dans ce qui suit:

  • Java: java.util.TreeMap,java.util.TreeSet
  • C ++ STL (dans la plupart des implémentations): map, multimap, multiset
  • Noyau Linux: planificateur complètement équitable, linux / rbtree.h
Nikunj Banka
la source
43
In general, the rotations for an AVL tree are harder to implement and debug than that for a Red-Black tree.ce n'est pas vrai.
Jingguo Yao
9
Pour être pédant, le standard C ++ ne l'exige pas std:: mapet les amis utilisent une structure particulière. C'est laissé à l'implémentation, bien que libstdc ++ et Dinkumware utilisent au moins des arbres rouge-noir, et il semble que vous ayez raison dans la pratique.
mbozzi
25
Le facteur d'équilibre stocké dans chaque nœud d'un arbre AVL est de deux bits (-1 / 0 / +1). Un arbre rouge-noir stocke un bit d'informations de couleur dans chaque nœud. Ainsi, au total, les deux arbres nécessitent une mémoire O (N) pour les informations supplémentaires.
Seppo Enarvi
5
"Pour une insertion de tâches intensives, utilisez un arbre rouge-noir." Pourquoi? L'insertion de l'arborescence AVL ne prend au pire qu'une rotation, tandis que l'arbre Red Black peut en prendre deux.
Daniel
3
Cela devrait être mis à jour selon l'analyse de 2003 de Ben Pfaff sur les performances de BST - les arbres AVL sont plus généraux et fonctionnent mieux. Les raisons historiques exactes pour lesquelles Java, C ++ et le noyau Linux choisissent une implémentation plus lente seraient intéressantes à rechercher.
David McManamon
16

Essayez de lire cet article

Il offre de bonnes informations sur les différences, les similitudes, les performances, etc.

Voici une citation de l'article:

Les RB-Trees sont, tout comme les arbres AVL, auto-équilibrés. Les deux fournissent des performances de recherche et d'insertion O (log n).

La différence est que les RB-Trees garantissent O (1) rotations par opération d'insertion. C'est ce qui coûte réellement la performance dans les implémentations réelles.

Simplifiés, les RB-Trees bénéficient de cet avantage en étant conceptuellement de 2-3 arbres sans entraîner la surcharge des structures de nœuds dynamiques. Physiquement, les RB-Trees sont implémentés sous forme d'arbres binaires, les drapeaux rouges / noirs simulent 2-3 comportements

D'après ma propre compréhension, les arbres AVL et RB ne sont pas très éloignés en termes de performances. Un arbre RB est simplement une variante d'un arbre B et l'équilibrage est implémenté différemment d'un arbre AVL.

Jordan
la source
1
AFIAK, un arbre AVL a également une rotation O (1) par insertion. Pour RB-tree et AVL - une insertion peut avoir 1 ou 0 rotation. Si une rotation se produit, les algorithmes s'arrêtent. Si cela ne se produit pas, les algorithmes continuent généralement à vérifier / repeindre les nœuds du bas à la racine de l'arbre. Ainsi, la rotation O (1) peut parfois être meilleure car elle élimine l'analyse des éléments restants O (log (n)). Parce que l'arbre AVL, en moyenne, fait plus de rotation, l'arbre AVL a généralement un meilleur équilibre ~ 1,44 log (N) que RB-tree 2 log (N).
Sergey Shandar
4

Notre compréhension des différences de performances s'est améliorée au fil des ans et maintenant, la principale raison d'utiliser des arbres rouge-noir sur AVL serait de ne pas avoir accès à une bonne implémentation AVL car ils sont légèrement moins courants, peut-être parce qu'ils ne sont pas couverts par CLRS.

Les deux arbres sont maintenant considérés comme des formes d' arbres à rang équilibré, mais les arbres rouge-noir sont systématiquement plus lents d' environ 20% dans les tests du monde réel . Ou même 30 à 40% plus lent lorsque des données séquentielles sont insérées .

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

David McManamon
la source
1
Drôle! dans ma lecture, l'article de libavl semble dire qu'AVL et RB sont en tête-à-tête, et ni l'un ni l'autre n'est très clairement meilleur que l'autre en général (lequel est le meilleur dépend de la charge de travail). Je ne vois nulle part une affirmation selon laquelle AVL est globalement environ 20% plus rapide.
Stefan
3

D'autres réponses ici résument bien les avantages et les inconvénients des arbres RB et AVL, mais j'ai trouvé cette différence particulièrement intéressante:

Les arbres AVL ne prennent pas en charge le coût de mise à jour amorti constant [mais les arbres rouge-noir le font]

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

Ainsi, alors que les arbres RB et AVL garantissent le moment le plus défavorable O (log (N)) pour la recherche, l'insertion et la suppression, la restauration de la propriété AVL / RB après l' insertion ou la suppression d'un nœud peut être effectuée en temps amorti O (1) pendant arbres rouge-noir.

emanek
la source
Je crois que l'insertion d'arbre AVL a le même coût amorti / similaire mais produit un arbre mieux équilibré (1,44log (N) vs 2log (N)). Dans le même temps, la suppression dans l'arborescence AVL peut nécessiter plus de rotations. À mon humble avis, ceci est traité dans WAVL en.wikipedia.org/wiki/WAVL_tree
Sergey Shandar
1

Les programmeurs n'aiment généralement pas allouer dynamiquement de la mémoire. Le problème avec l'arborescence avl est que pour "n" éléments, vous avez besoin d'au moins log2 (log2 (n)) ... (height-> log2 (n)) bits pour stocker la hauteur de l'arbre! Ainsi, lorsque vous manipulez d'énormes données, vous ne pouvez pas être sûr du nombre de bits à allouer pour stocker la hauteur à chaque nœud.

Par exemple, si vous utilisez 4 octets int (32 bits) pour stocker la hauteur. La hauteur maximale peut être: 2 ^ 32 et donc le nombre maximum d'éléments que vous pouvez stocker dans l'arbre est de 2 ^ (2 ^ 32) - (semble être très grand mais à l'ère des données, rien n'est trop grand je suppose). Et par conséquent, si vous dépassez cette limite, vous devez allouer dynamiquement plus d'espace pour stocker la hauteur.

C'est une réponse suggérée par un professeur de mon université qui m'a paru raisonnable! J'espère avoir du sens.

Modifications: les arbres AVL sont plus équilibrés que les arbres noirs rouges, mais ils peuvent entraîner plus de rotations lors de l'insertion et de la suppression. Donc, si votre application implique de nombreuses insertions et suppressions fréquentes, les arbres Red Black devraient être préférés. Et si les insertions et suppressions sont moins fréquentes et que la recherche est une opération plus fréquente, alors l'arborescence AVL doit être préférée à l'arbre rouge noir. --Source GEEKSFORGEEKS.ORG

Prakhar Agrawal
la source
1
Je dirais que c'est intéressant mais peu pratique. S'il est vrai que dans le cas le plus compact, il serait difficile de choisir le nombre de bits le plus efficace à allouer pour la hauteur, en pratique, tout espace restant inférieur à un octet sera définitivement inutilisé, et tout ce qui reste dans un espace de 4 ou même 8 octets sera presque certainement inutilisé. La mémoire n'est pas allouée non alignée pour des raisons de performances qui annulent considérablement l'avantage de récupérer une petite quantité d'espace. Les pointeurs vers les enfants et la valeur occupent 24 octets; Il est peu probable que 8 autres aient un coût pratique.
Mumbleskates
4
you need need atleast log2(log2(n))...(height->log2(n)) bits to store the height of [an AVL] treeJe n'ai besoin de la hauteur d'aucun nœud dans un arbre AVL pour l'implémenter. Vous avez besoin d' un peu d'informations supplémentaires pour chaque nœud ( JE SUIS LE PLUS GRAND (le frère avec le sous-arbre le plus élevé))); il est plus pratique et conventionnel d'avoir deux bits supplémentaires (l'enfant est plus haut pour la gauche et la droite), comme présenté par AV & L.
greybeard
4
2 ^ (2 ^ 32) éléments, c'est beaucoup ... comme si vous pouviez stocker chaque molécule dans l'univers entier, et chaque paire possible de ces molécules, et chaque triple possible, et toujours même pas commencer à se rapprocher même à distance de se situant dans une infime fraction d'un minuscule pourcentage de la racine cubique de ce nombre divisé par cent quintillions.
point
4
Ceci est très trompeur. Premièrement, 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 la quantité typique de mémoire disponible double chaque année, nous avons encore 4 milliards d'années jusqu'à ce que la hauteur de nos arbres dépasse ce qui peut être stocké en 32 bits.
Gassa
3
2 ^ (2 ^ 32) objets est ridiculement, incroyablement, absolument plus que n'importe quel ordinateur que nous pouvons imaginer maintenant ne peut jamais contenir. Nous sommes à quelque chose comme 2 ^ 40. Vérifiez à nouveau que vous êtes mathématique.
Stefan Reich du
-1

Le rééquilibrage de l'arborescence AVL doit respecter la propriété ci-dessous. (Référence Wiki - Arbre AVL )

Dans une arborescence AVL, les hauteurs des deux sous-arbres enfants de n'importe quel nœud diffèrent d'au plus un; si à tout moment ils diffèrent de plus d'un, un rééquilibrage est effectué pour restaurer cette propriété.

Cela implique donc que la hauteur totale de l'arbre AVL ne peut pas devenir folle, c'est-à-dire que les recherches seront meilleures avec les arbres AVL. Et comme des opérations supplémentaires (rotations) doivent être effectuées pour ne pas laisser la hauteur devenir folle, les opérations de modification d'arbre peuvent être un peu coûteuses.

samshers
la source
Il est mentionné de nombreux autres endroits, mais la raison pour laquelle cette réponse n'est pas très bonne est que les arbres AVL et les arbres RB maintiennent effectivement des contraintes extrêmement similaires - les arbres RB ne seront pas plus de 2,0 fois la hauteur requise, et pour les arbres AVL, ce facteur est vers 1,44. Les arbres AVL tournent un peu plus souvent en conséquence, mais le coût par rotation est essentiellement le même; ce n'est pas coûteux.
Mumbleskates