Les arbres AVL et Red black sont tous deux auto-équilibrés, à l'exception de la couleur rouge et noire dans les nœuds. Quelle est la principale raison de choisir les arbres Red black au lieu des arbres AVL ? Quelles sont les applications des arbres rouges noirs ?
Quelle est la principale raison de choisir des arbres rouges noirs plutôt que des arbres AVL ?
Les deux sites arbres rouges-noirs y Arbres AVL sont les plus couramment utilisés arbres de recherche binaires équilibrés et ils supportent l'insertion, la suppression et la recherche dans des conditions garanties. O(logN) time . Cependant, il existe des points de comparaison entre les deux :
O(N) espace supplémentaire. Toutefois, si nous savons que les clés qui seront insérées dans l'arbre seront toujours supérieures à zéro, nous pouvons 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.Quelles sont les applications de l'arbre noir rouge ?
Les arbres rouge-noir sont plus généraux. Ils sont relativement efficaces pour l'ajout, la suppression et la consultation, mais les arbres AVL ont des consultations plus rapides au prix d'un ajout/suppression plus lent. L'arbre rouge-noir est utilisé dans les cas suivants :
java.util.TreeMap , java.util.TreeSet
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'impose pas que std:: map et 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 en pratique.
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'information sur la couleur dans chaque nœud. Ainsi, au total, les deux arbres nécessitent O(N) de mémoire pour les informations supplémentaires.
Essayez de lire ceci article
Il offre un bon aperçu des différences, des similitudes, des performances, etc.
Voici une citation de l'article :
Les arbres RB sont, tout comme les arbres AVL, auto-équilibrés. Ils offrent tous deux des performances de consultation et d'insertion de O(log n).
La différence est que les arborescences RB garantissent O(1) rotations par opération d'insertion. C'est ce qui coûte réellement les performances dans les implémentations réelles.
Simplifiés, les arbres RB ont l'avantage d'être conceptuellement 2 ou 3 arbres sans avoir à supporter la surcharge des structures de nœuds dynamiques. Physiquement, les arborescences RB sont implémentées comme des arbres binaires, les drapeaux rouge/noir simulent le comportement 2-3.
D'après ce que je comprends, les arbres AVL et les arbres 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 mis en œuvre différemment d'un arbre AVL.
AFIAK, un arbre AVL a également O(1) rotation par insertion. Pour RB-tree et AVL - une insertion peut avoir 1 ou 0 rotations. Si une rotation se produit, les algorithmes s'arrêtent. Si elle ne se produit pas, les algorithmes continuent généralement à vérifier/repeindre les nœuds du bas vers la racine de l'arbre. Ainsi, parfois, une rotation O(1) peut ê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 est, généralement, a un meilleur équilibre ~1.44 log(N) que l'arbre RB 2 log(N).
Notre compréhension des différences de performance s'est améliorée au fil des ans et aujourd'hui, la principale raison d'utiliser les arbres rouge-noir plutôt que les AVL serait de ne pas avoir accès à une bonne implémentation des 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 de arbres à rangs équilibrés mais les arbres rouge-noir sont systématiquement plus lents en environ 20% dans les tests en conditions réelles . Ou même 30-40% plus lent lorsque des données séquentielles sont insérées .
Ainsi, les personnes qui ont étudié les arbres rouge-noir mais pas les arbres AVL ont tendance à choisir les arbres rouge-noir. Les principaux usages des arbres rouge-noir sont détaillés sur le site Web de la Commission européenne. Entrée Wikipedia pour eux .
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 supportent pas les constantes coût amorti de la mise à jour [mais les arbres rouges et noirs le font]
Source : Mehlhorn & Sanders (2008) (section 7.4)
Ainsi, alors que les arbres RB et AVL garantissent tous deux un temps O(log(N)) dans le pire des cas pour la consultation, 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 O(1) temps amorti pour les arbres rouge-noir.
Je pense que l'insertion de l'arbre AVL a un coût amorti identique/similaire mais produit un arbre mieux équilibré (1,44log(N) contre 2log(N)). Dans le même temps, la suppression dans l'arbre AVL peut nécessiter plus de rotations. À mon avis, ce problème est traité dans WAVL. fr.wikipedia.org/wiki/WAVL_tree
Les insertions dans les arbres AVL et dans les arbres RB nécessitent toutes deux un maximum de 2 rotations. À partir de https://adtinfo.org/ :
Le principal avantage des arbres rouge-noir est que, dans les arbres AVL, la suppression d'un nœud d'un arbre contenant n nœuds peut nécessiter log 2 n rotations, mais la suppression dans un arbre rouge-noir ne nécessite jamais plus de trois rotations.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
2 votes
Duplication possible de Pourquoi std::map est-il implémenté comme un arbre rouge-noir ?
2 votes
Pour l'anecdote, les développeurs de Rust ont choisi d'utiliser un fichier Arbre B au lieu de l'un ou l'autre pour leur carte ordonnée standard.