Admin CliCours
Cours avantages et inconvénients d’un ABR (Arbre Binaire de Recherche), tutoriel & guide de travaux pratiques en pdf.
Arbres AVL
Avantages et inconvénients d’un ABR:
Très efficace pour les insertions et suppressions mais s’ils sont complètement déséquilibrés ils transforment la recherche en algorithme O(n) (cas des arbres dégénérés)
Solution : Éviter les variations dans les longueurs des branches de l’arbre :
Première idée : arbres complètement équilibrés : très coûteux pour les insertions et les suppressions
Deuxième idée : arbres AVL (Adelson-Velsskii-Landis) : AB équilibrés tel que pour chaque nœud les hauteurs de ses deux sous arbres gauche et droit diffèrent au plus de 1
Arbre AVL : insertion (1)
Première étape : ajouter le nouveau nœud dans l’arbre comme s’il s’agit d’une insertion dans ABR. Le chemin de la racine au nouveau nœud est appelé chemin de recherche Deuxième étape : MAJ les champs BAL de tous les nœuds du chemin de recherche Troisième étape : Vérifier si l’arbre est AVL. Si l’arbre est déséquilibré le rendre AVL.
Arbre AVL : insertion (5)
Un arbre est déséquilibré si certains de ses sous arbres ont un déséquilibre supérieur à 1 en valeur absolue (-2 ou +2)
-a- Soit A le plus petit de ces sous arbres cad A est tel que ses SAG et SAD sont équilibrés
-b- Transformer A pour le rendre équilibré
-c- En rendant A équilibré cela ne veut pas dire que l’arbre complet est devenue équilibré dans ce cas il faut recommencer la transformation (étape (a))
……
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)Cours sur Arbre AVL arbre de recherche binaire équilibré (196 Ko) (Cours PDF)
