2
Quelle est la différence entre WAVL (faible AVL) et Red Black Tree? Y at-il une raison spécifique d'utiliser WAVL sur RB?Quelle est la différence entre WAVL (faible AVL) et Red Black Tree?
A
Répondre
1
Un arbre WAVL est une tentative de combiner les meilleures caractéristiques d'un arbre AVL et d'arbres rouge-noir. Juste l'insertion dans un arbre WAVL va construire le même arbre qu'un arbre AVL - un arbre qui est plus strictement équilibré qu'un arbre rouge-noir, donc les arbres WAVL peuvent être mieux performants dans des situations où les arbres rouge-noir deviennent plus déséquilibrés. Supprimer dans WAVL est légèrement plus simple que supprimer pour les arbres AVL en ce que les suppressions WAVL effectuent seulement 1 ou 2 rotations et s'arrêtent au lieu de potentiellement jusqu'à la racine.
+0
C'est simple à dire, mais il n'y a rien qui explique le WAVL sur le web pour qui peut nous aider à valider la vérité sur leur algorithme. –
+0
Je pense que nous pouvons trouver toutes les informations dont vous avez besoin sur le web concernant les arbres WAVL. Quelle vérité voulez-vous valider? Le document original à leur sujet couvre tous les détails et la performance est similaire à celle des arbres AVL qui sont couverts dans l'article de Ben Pfaff de 2004 (AVL 20% plus rapide que le rouge-noir). –
+0
Merci. J'aurais aimé lire le document original qui explique en détail toutes les règles. Aussi, vous faites référence à AVL 20% plus rapide que Red Black Tree. Cela me semble bizarre car il y a beaucoup de variables qui pourraient affecter les performances comme l'utilisation de la récursion ou de l'itération, la façon dont vous générez un nouveau nœud (d'une banque ou non), ce que vous faites: Les deux implémentations ont-elles partagé les mêmes optimisations. Je serais ravi d'inclure une référence (lien) dans votre réponse si vous en avez. Le semble ne pas être accessible ??? –
Bonjour, Bienvenue dans Stack Overflow. Sachez que les réponses à cette question peuvent entraîner des réponses qui ne sont pas entièrement basées sur des faits ou des réponses biaisées en raison de préférences personnelles. Il est possible qu'il existe différents cas d'utilisation où chaque option serait mieux adaptée à un objectif donné. Pour recevoir une réponse à ce sujet, pensez à ajouter plus de détails à la question en indiquant comment vous voulez l'utiliser et pourquoi vous pensez que chaque option répond ou non à vos besoins. J'espère que vous êtes en mesure de trouver quelle option vous convient le mieux :) –