Différence entre les arbres rouge-noir et les arbres AVL

Question

Quelqu'un peut-il expliquer quelles sont les principales différences entre ces deux structures de données ? J'ai essayé de trouver une source en ligne qui souligne les différences/similitudes, mais je n'ai rien trouvé de très instructif. Dans quels cas l'une serait-elle préférable à l'autre ? Dans quelles situations pratiques l'une est-elle "meilleure" que l'autre ?

Answer 1

Les arbres AVL maintiennent un équilibre plus rigide que les arbres rouge-noir. Le chemin entre la racine et la feuille la plus profonde d'un arbre AVL est au maximum de ~1,44 lg(n+2), alors qu'il est au maximum de ~2 lg (n+1) dans les arbres rouge-noir.

Par conséquent, la consultation d'un arbre AVL est généralement plus rapide, mais au prix d'une insertion et d'une suppression plus lentes en raison d'un plus grand nombre d'opérations de rotation. Utilisez donc un arbre AVL si vous pensez que le nombre de consultations dominera le nombre de mises à jour de l'arbre.

Answer 2

Pour les petites données :

insérer : L'arbre RB et l'arbre avl ont un nombre constant de rotations maximales mais l'arbre RB sera plus rapide parce qu'en moyenne l'arbre RB utilise moins de rotations.

consultation : L'arbre AVL est plus rapide, car l'arbre AVL a moins de profondeur.

supprimer : L'arbre RB a un nombre constant de rotations maximales mais l'arbre AVL peut avoir O(log N) fois des rotations comme pire. et en moyenne l'arbre RB a aussi moins de rotations donc l'arbre RB est plus rapide.

pour les données volumineuses :

insérer : L'arbre AVL est plus rapide, car il faut rechercher un nœud particulier avant l'insertion. Au fur et à mesure que les données augmentent, la différence de temps pour rechercher le nœud particulier est proportionnelle à O(log N), mais l'arbre AVL et l'arbre RB ne nécessitent toujours qu'un nombre constant de rotations dans le pire des cas. Le goulot d'étranglement devient donc le temps de recherche de ce nœud particulier.

consultation : L'arbre AVL est plus rapide. (comme dans le cas des petites données)

supprimer : L'arbre AVL est plus rapide en moyenne, mais dans le pire des cas, l'arbre RB est plus rapide, car il faut également rechercher un nœud très profond à échanger avant de l'enlever (comme pour l'insertion).

Answer 3

Citation de ce texte : Différence entre les arbres AVL et les arbres rouge-noir

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 arbres RB garantissent O(1) rotations par opération d'insertion. C'est ce qui coûte réellement la performance i Simplifiés, les RB-Trees tirent cet avantage du fait qu'ils sont conceptuellement 2 ou 3 arbres, sans avoir à supporter la surcharge des structures de nœuds dynamiques. Physiquement, les RB-Trees sont implémentés comme des arbres binaires, les drapeaux rouges/noirs simulent le comportement 2-3.

par définition, tout AVL est donc un sous-ensemble de Rouge-Noir. On devrait pouvoir colorer n'importe quel arbre AVL, sans restructuration ni rotation, pour le transformer en arbre Rouge-Noir.

Answer 4

Les arbres AVL sont souvent comparés aux arbres rouge-noir parce qu'ils prennent en charge le même ensemble d'opérations et qu'ils prennent O(log n) temps pour les opérations de base. Pour les applications à forte intensité de recherche, AVL tμμ≤½

F A

Answer 5

Pour avoir une idée du fonctionnement d'un arbre AVL, este la visualisation interactive aide.

AVL et RedBlack Trees sont des structures de données arborescentes équilibrées en hauteur. Ils sont assez similaires, et la véritable différence réside dans le nombre d'opérations de rotation effectuées lors de chaque opération d'ajout/suppression - plus élevé dans le cas de l'AVL, afin de préserver un équilibrage global plus homogène.

Les deux implémentations sont mises à l'échelle en tant que O(lg N) où N est le nombre de feuilles, mais dans la pratique, un arbre AVL est plus rapide pour les tâches intensives de recherche : grâce à un meilleur équilibrage, les traversées de l'arbre sont en moyenne plus courtes. D'autre part, en ce qui concerne l'insertion et la suppression, un arbre AVL est plus lent : un plus grand nombre de rotations est nécessaire pour rééquilibrer correctement la structure de données en cas de modification.

Pour les implémentations générales (c'est-à-dire qu'a-priori il n'est pas clair si les consultations sont les opérations prédominantes), les arbres RedBlack sont préférables : ils sont plus faciles à implémenter et plus rapides dans les cas courants - lorsque la structure de données est modifiée aussi fréquemment que l'on effectue des recherches. Un exemple, TreeMap y TreeSet en Java utilisent un arbre RedBlack de soutien.