Arbre noir rouge sur arbre avl

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

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

Les arborescences rouge-noir et les arborescences AVL sont les arborescences binarys équilibrées les plus utilisées et elles prennent en charge l’insertion, la suppression et la O(logN) time . Cependant, il existe des points de comparaison suivants entre les deux:

  • Les arbres AVL sont plus rigoureusement équilibrés et fournissent donc des recherches plus rapides. Ainsi, pour une tâche intensive de recherche, utilisez un arbre AVL.
  • Pour une insertion de tâches intensives, utilisez un arbre rouge-noir.
  • Les arbres AVL stockent le facteur d’équilibre sur chaque nœud. Cela prend O(N) extra space . Cependant, si nous soaps 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 prend O(1) extra space .
  • En général, les rotations pour un arbre AVL sont plus difficiles à implémenter et à déboguer que pour un arbre Rouge-Noir.

Quelles sont les applications de l’arbre noir rouge?

Les arbres rouge-noir sont plus généraux. Ils se comportent relativement bien lors de l’ajout, de la suppression et de la consultation, mais les arborescences AVL ont des recherches plus rapides au prix d’un ajout / retrait plus lent. L’arbre rouge-noir est utilisé dans les cas suivants:

  • Java: java.util.TreeMap, java.util.TreeSet.
  • C ++ STL: map, multimap, multiset.
  • Noyau Linux: ordonnanceur complètement correct, linux / rbtree.h

Essayez de lire cet article

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

Voici une citation de l’article:

Les arbres RB sont, ainsi que 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 arbres RB garantissent des rotations O (1) par opération d’insertion. C’est ce qui coûte réellement la performance dans les implémentations réelles.

Simplifié, les arborescences RB tirent cet avantage de leur conceptalité consistant en 2 ou 3 arbres sans contourner la surcharge des structures de nœuds dynamics. Physiquement, les arbres RB sont implémentés en tant qu’arbres binarys, les drapeaux rouge / noir simulent un comportement 2-3

À mon sens, les arbres AVL et les arbres RB ne sont pas très éloignés en termes de performances. Une arborescence RB est simplement une variante d’une arborescence B et l’équilibrage est implémenté différemment d’une arborescence AVL.

Le rééquilibrage de l’arborescence AVL doit correspondre à la propriété ci-dessous. (Référence Wiki – Arbre AVL )

Dans un arbre AVL, les hauteurs des deux sous-arbres enfants d’un 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’arborescence 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 de l’arbre peuvent être peu coûteuses.

Notre compréhension des différences de performance s’est améliorée au fil des ans et la principale raison d’utiliser les arbres rouge-noir sur AVL ne serait pas d’avoir access à une bonne implémentation AVL puisqu’elles sont légèrement moins courantes, peut-être parce qu’elles ne sont pas couvertes par CLRS.

Les deux arbres sont maintenant considérés comme des formes d’ arbres équilibrés, mais les arbres rouges-noirs sont systématiquement plus lents d’ environ 20% lors d’essais réels . 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 des arbres rouge-noir. Les utilisations principales pour les arbres rouge-noir sont détaillées sur l’entrée Wikipedia pour eux .

Les programmeurs n’aiment généralement pas allouer dynamicment de la mémoire. Le problème avec l’arbre avl est que pour “n” éléments, il faut au moins log2 (log2 (n)) … (height-> log2 (n)) bits pour stocker la hauteur de l’arbre! Ainsi, lorsque vous manipulez des données énormes, vous ne pouvez pas être sûr du nombre de bits à atsortingbuer 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 en cette ère de données, rien n’est trop grand, je suppose). Et par conséquent, si vous dépassez cette limite, vous devez allouer dynamicment plus d’espace pour stocker la hauteur.

C’est une réponse suggérée par un professeur de mon université qui me semblait raisonnable! J’espère que j’ai du sens.

Modifications: Les arbres AVL sont plus équilibrés que les arbres rouges noirs, mais ils peuvent provoquer 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 les suppressions sont moins fréquentes et que la recherche est une opération plus fréquente, l’arborescence AVL doit être préférée à l’Arbre Noir Rouge. –Source GEEKSFORGEEKS.ORG

D’autres réponses 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 les coûts de mise à jour amortis constants [mais les arbres rouges-noirs le font]

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

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