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

Quelqu’un peut-il s’il vous plaît 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 et les similitudes, mais je n’ai rien trouvé de très instructif. Dans quels cas l’un serait-il préféré à l’autre? Quelles situations pratiques rendent un “meilleur” à utiliser que l’autre?

Les arbres AVL maintiennent un équilibre plus rigide que les arbres rouge-noir. Le chemin de la racine à la feuille la plus profonde dans un arbre AVL est au maximum de ~ 1,44 lg (n + 2), tandis que dans les arbres rouges-noirs, il atteint au maximum ~ 2 lg (n + 1).

En conséquence, la recherche dans une arborescence AVL est généralement plus rapide, mais cela se traduit par une insertion et une suppression plus lentes dues à des opérations de rotation plus importantes. Utilisez donc un arbre AVL si vous prévoyez que le nombre de recherches domine le nombre de mises à jour de l’arborescence.

En citant ceci: Différence entre AVL et arbres rouge-noir

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.

par définition, chaque AVL est donc un sous-ensemble de Red-Black. On devrait pouvoir colorer n’importe quel arbre AVL, sans restructuration ni rotation, pour le transformer en arbre rouge-noir.

Les arborescences AVL sont souvent comparées aux arborescences rouge-noir car les deux prennent en charge le même ensemble d’opérations et prennent du temps O(log n) pour les opérations de base. Pour les applications nécessitant une recherche intensive, les arbres AVL sont plus rapides que les arbres rouge-noir, car ils sont mieux équilibrés. Semblable aux arbres rouge-noir, les arbres AVL sont équilibrés en hauteur. Les deux ne sont généralement pas équilibrés ni μ-équilibrés pour aucun μ ≤ ½; c’est-à-dire que les nœuds frères peuvent avoir des nombres de descendants très différents.

De l’article de Wikipedia sur les arbres AVL

La hauteur maximale des arbres est primordiale pour garder l’équilibre. Cela équivaut presque à 1.44 * log(n) pour AVL, mais pour RB tree, il s’agit de 2 * log(n) . Nous pouvons donc conclure qu’il est préférable d’utiliser l’AVL lorsque le problème est l’incitation à la recherche. Ce qui compte, c’est une autre question pour AVL et RB Tree. L’arborescence RB est meilleure que l’AVL face à l’insertion aléatoire au moindre coût de la rotation mais l’AVL qui permet d’insérer les données ascendantes ou descendantes. Donc, si le problème est l’incitation à l’insertion, nous pouvons utiliser l’arborescence RB.

D’après ce que j’ai vu, il semble que les arbres AVL effectuent autant de rotations (parfois de manière récursive dans l’arbre) que nécessaire pour obtenir la hauteur désirée de l’arbre AVL (Log n). Cela le rend plus équilibré.

Pour les Arbres Noirs Rouges, il existe 5 ensembles de règles dont vous avez besoin pour restr en place tout au long de l’insertion et de la suppression, que vous pouvez trouver ici http://en.wikipedia.org/wiki/Red-black_tree .

La principale chose qui pourrait vous aider pour les arbres rouges noirs est le fait que selon ces cinq règles, vous pouvez colorier récursivement l’arbre jusqu’à la racine si l’oncle est rouge. Si l’oncle est noir, vous devrez effectuer un maximum de deux rotations pour résoudre les problèmes que vous rencontrez, mais après ces deux rotations, VOUS ÊTES FAIT. Emballez-le et dites bonne nuit car c’est la fin de la manipulation que vous devez faire.

La règle Big est le numéro 5 … “Chaque chemin simple entre un nœud donné et l’une de ses feuilles descendantes contient le même nombre de nœuds noirs”.

Cela provoquera la plupart des rotations dont vous aurez besoin pour que l’arbre fonctionne et que l’arbre ne soit pas trop déséquilibré.

En résumé: AvlTrees est légèrement mieux équilibré que RedBlackTrees. Les deux arbres prennent globalement le temps O (log n) pour les recherches, les insertions et les suppressions, mais pour l’insertion et la suppression, le premier requirejs des rotations O (log n), tandis que le second ne prend que des rotations O (1).

Étant donné que les rotations signifient écrire en mémoire et que l’écriture en mémoire est coûteuse, RedBlackTrees est en pratique plus rapide à mettre à jour que AvlTrees.

Le fait que les arbres RedBlack aient moins de rotations peut les rendre plus rapides pour les insertions / suppressions, cependant …. Comme ils sont généralement un peu plus profonds, ils peuvent également être plus lents sur les inserts et les suppressions. Chaque fois que vous passez d’un niveau à un autre dans l’arborescence, il y a un grand changement: les informations demandées ne sont pas dans le cache et doivent être extraites de la RAM. Ainsi, le temps gagné sur moins de rotations peut déjà être perdu car il doit naviguer plus profondément et donc mettre à jour son cache plus souvent. Pouvoir opérer à partir du cache fait une grande différence. Si les informations pertinentes sont en cache, vous pouvez effectuer plusieurs opérations de rotation, dans le temps nécessaire pour naviguer dans un niveau supplémentaire et les informations de niveau suivant ne sont pas en cache. Ainsi, dans les cas où RedBlack est en théorie plus rapide, en ne regardant que les opérations nécessaires, il pourrait être plus lent dans la pratique, en raison d’un manque de cache.

Pour avoir une idée du fonctionnement d’un arbre AVL, cette visualisation interactive aide.

L’AVL ainsi que les arbres RedBlack sont des structures de données arborescentes équilibrées. Ils sont assez similaires et la véritable différence réside dans le nombre d’opérations de rotation effectuées lors de toute opération d’addition / suppression – plus élevée dans le cas de l’AVL, afin de préserver un équilibrage global plus homogène.

Les deux implémentations sont dimensionnées en O(lg N) , où N est le nombre de feuilles, mais en pratique, une arborescence AVL est plus rapide pour les tâches de recherche intensives: profitant d’un meilleur équilibrage, les parcours de l’arbre sont en moyenne plus courts. D’un autre côté, l’insertion et la suppression sont plus lentes: un nombre plus élevé de rotations est nécessaire pour rééquilibrer correctement la structure de données lors de la modification.

Pour les implémentations à usage général (c’est-à-dire a priori on ne sait pas si les recherches sont la prédominance des opérations), les arborescences RedBlack sont préférées: elles sont plus faciles à implémenter et plus rapides dans les cas courants . Un exemple, TreeMap et TreeSet en Java utilisent un arbre de sauvegarde RedBlack.