Un Arbre AVL défini comme un auto-équilibrage La différence entre les hauteurs du sous-arbre gauche et du sous-arbre droit pour n'importe quel nœud est connue sous le nom de facteur d'équilibre du nœud.
L'arbre AVL doit son nom à ses inventeurs, Georgy Adelson-Velsky et Evgenii Landis, qui l'ont publié dans leur article de 1962 Un algorithme pour l'organisation de l'information.
Exemple d'arbres AVL :
Arbre AVL
L'arbre ci-dessus est AVL car les différences entre les hauteurs des sous-arbres gauche et droit pour chaque nœud sont inférieures ou égales à 1.
Opérations sur une arborescence AVL :
Rotation des sous-arbres dans une arborescence AVL :
Un arbre AVL peut pivoter de l'une des quatre manières suivantes pour rester en équilibre :
Rotation à gauche :
Lorsqu'un nœud est ajouté dans le sous-arbre droit du sous-arbre droit, si l'arbre est déséquilibré, nous effectuons une seule rotation vers la gauche.
Rotation à gauche dans l'arborescence AVL
Rotation à droite :
Si un nœud est ajouté au sous-arbre gauche du sous-arbre gauche, l'arbre AVL peut se déséquilibrer, nous effectuons une seule rotation vers la droite.
Rotation à droite dans l'arborescence AVL
Rotation gauche-droite :
Une rotation gauche-droite est une combinaison dans laquelle la première rotation à gauche a lieu après l'exécution de la rotation à droite.
Rotation gauche-droite dans l'arborescence AVL
Rotation droite-gauche :
Une rotation droite-gauche est une combinaison dans laquelle la première rotation à droite a lieu après l'exécution de la rotation à gauche.
Rotation droite-gauche dans l'arborescence AVL
Applications de l'arbre AVL :
- Il est utilisé pour indexer d’énormes enregistrements dans une base de données et également pour y effectuer une recherche efficace.
- Pour tous les types de collections en mémoire, y compris les ensembles et les dictionnaires, les arborescences AVL sont utilisées.
- Applications de base de données, où les insertions et les suppressions sont moins courantes mais où des recherches de données fréquentes sont nécessaires
- Logiciel nécessitant une recherche optimisée.
- Il est appliqué dans les domaines d'entreprise et dans les jeux de scénario.
Avantages de l’arbre AVL :
- Les arbres AVL peuvent s’auto-équilibrer.
- Ce n’est sûrement pas biaisé.
- Il fournit des recherches plus rapides que les arbres rouge-noir
- Meilleure complexité du temps de recherche par rapport à d'autres arbres comme l'arbre binaire.
- La hauteur ne peut pas dépasser log(N), où N est le nombre total de nœuds dans l'arborescence.
Inconvénients de l’arbre AVL :
- C’est difficile à mettre en œuvre.
- Il présente des facteurs constants élevés pour certaines opérations.
- Moins utilisé que les arbres rouge-noir.
- En raison de leur équilibre plutôt strict, les arbres AVL fournissent des opérations d'insertion et de retrait compliquées à mesure que davantage de rotations sont effectuées.
- Prenez plus de traitement pour l'équilibrage.
Articles Liés:
- Introduction aux arbres de recherche binaires – Tutoriels sur la structure des données et les algorithmes
- Insertion dans une arborescence AVL
- Suppression dans une arborescence AVL
