AVL
Arbre binaire équilibré
NOM DES EXPOSANTS:
• KOULLO LOUBA-NDEM
• NDORELEMBAYE BATISTA
Chargé de cours : Dr Mahamat Atteib Ibrahim Doutoum
INTRODUCTION
Créé par Adelson-Velskii et Landis (1962)
On appelle arbre AVL tout ABR tel que, pour tout
sommet, la différence des hauteurs des sous-arbre
gauche et droit est en valeur absolue inférieure ou
égale à 1.
PRINCIPE DE AVL
En chaque sommet, on mesure
l’équilibre = ht(filsdroit) − ht(filsgauche)
Cette mesure ne peut valoir que 1, -1 ou 0.
Avantages :
Algorithme d’insertion (complexe mais) facile `a implémenter
Garantie de recherche en O(logn)
Les operations sur l’arbre AVL
Les opérations possibles sur un AVL sont :
Ajout d’un élément
Suppression d’un élément
cf( arbre binaire de recherche)
1. Le rééquilibrage
Un principe : la rotation.
En fait, selon le facteur de déséquilibrage de l’arbre et celui de ses
sous-arbres, on va devoir faire une ou deux rotations:
• Rotation à droite;
• Rotation à gauche;
•Rotation double(gauche-droite, droite-gauche).
Principe de la rotation à droite
Le principe de la rotation est simple, il consiste à pivoter
les sommets sur un sommet appelé pivot (un axe). Le pivot
devient la racine et l’ancienne racine devient le fils droit
du pivot, le fils droit du pivot devient le fils gauche de
l’ancienne racine.
Rotation à droite
Le principe la rotation à gauche
Le principe de la rotation consiste à pivoter les
sommets sur un sommet appelé pivot (un axe). Le
pivot devient la racine et l’ancienne racine
devient le fils gauche du pivot, le fils gauche du
pivot devient le fils droit de l’ancienne racine.
Rotation à gauche
Principe de la rotation double
Tout comme la rotation à gauche et la rotation à droite
la rotation double a le même principe. Comme son nom
l’indique la rotation double fait deux (2) rotation.
La rotation double à droite: fait une rotation simple à
gauche puis une simple à droite;
La rotation double à gauche: elle fait une rotation
simple à droite puis une simple à gauche;
Double rotation
Algorithme
Si B est un arbre AVL et si on ajoute ou supprime un sommet à B,
alors
si aucun déséquilibre, on a toujours un AVL.
sinon soit x le sommet le plus bas déséquilibre(2 ou -2):
si x a un déséquilibre de -2 et est tel que son fils gauche soit
-a un déséquilibre de -1, alors une rotation rd(x,B)
-a un déséquilibre de 1, alors une rotation rgd(x,B)
si x a un déséquilibre de 2 et est tel que son fils droit
a un déséquilibre de 1, alors une rotation rg(x,B)
a un déséquilibre de -1, alors une rotation rdg(x,B)
Pseudo-code :
Fonction équilibrer(A: ABR): AVL
Début
Si |ecart(A)| <= 1 Alors
Retourner A
Sinon Si ecart(A) = -2
Si ecart(fG(A)) = -1 Alors
Retourner rotDroite(A)
Sinon { ecart(fG(A)) = 1 }
Retourner rotGaucheDroite(A)
FinSi
Sinon {ecart(A) = 2 }
Si ecart(fD(A)) = 1 Alors
Retourner rotGauche(A)
Sinon { ecart(fD(A)) = -1 }
Retourner rotDroiteGauche(A)
FinSi
FinSi
Fin
Exemple
1- Créer un arbre AVL en ajoutant successivement les
nombres 12, 3, 2, 5, 4, 7, 9, 11, 14 et 10.
2- Créer un arbre AVL 2,1,5,3,7,9,6,10,8,11
Corrigé
Suite
Suite
Suite
Merci pour votre aimable
attention!!