10. AVL (ABR équilibré)
Cf. TD5
On souhaite améliorer nos ABR et éviter d’avoir des arbres trop “allongés” (genre file de fer) -> on veut des arbres avec une hauteur pas trop grande pour une taille donnée.
Définition
Taille d’un arbre
La taille d’un arbre est le nombre de noeud
Arbre binaire équilibré
On dit qu’un arbre binaire équilibré si :
- c’est l’arbre vide
- le sous-arbre de gauche et le sous-arbre de droite soit équilibré
- La différence de hauteur entre le sous-arbre de gauche et le sous-arbre de droite est strictement inférieure à deux en valeur absolue.
Exemple :
- La différence de hauteur entre le sous-arbre de gauche et le sous-arbre de droite est strictement inférieure à deux en valeur absolue.
Théorème
La hauteur d’un arbre équilibré de taille n est inférieure à 2\times log_e(n).
On souhaite utiliser et maintenir des ABR équilibrés. Pour cela on conserve dans chaque noeud A la hauteur du sous-arbre dont la racine est le noeud A. À chaque ajout ou suppression d’un noeud, s’il provoque un déséquilibre, on effectuera une “rotation d’arbre” pour le rendre équilibré.
Définition
AVL
Un AVL (nom des concepteurs) est un ABR (Arbre Binaire de Recherche) équilibré.
Après un ajout simple ou une suppression simple dans un AVL, s’il y a déséquilibre la différence de hauteur ne peut-être plus de 2.
Rotation
Remarques
Une rotation conserves :
- les étiquettes des noeuds
- la structure ABR
Une rotation réduit une des hauteurs
Sur la hauteur
Remarques
Chaque ajout ou suppression entraînera soit :
- 0 rotation
- 1 rotation simple
- 1 rotation double
Amélioration
La hauteur mémorisé peut-être remplacé par la différence de hauteur entre le sous-arbre droit et celui de gauche. (-1, 0, -1, soit 2 bits).
Preuves
Arbre complet
Définition
Un arbre complet de hauteur h est un arbre qui contient le maximum de noeud pour sa hauteur.
Propriété
La taille d’un arbre complet de hauteur h est 2^{h+1}-1
Hauteur complète
Définition
Soit un arbre A sa hauteur complète la hauteur de son plus grand sous-arbre :
- ayant la même racine que A
- complet
Exemple
Lemme
La hauteur complète d’un arbre équilibré de hauteur h est supérieur à \dfrac{h}{2}
Preuve du théorème
Soit A un arbre équilibré de taille n et de hauteur h, alors selon le lemme :
2^{\frac{h}{2}+1} \leq n \leq 2^{h+1}
\frac{h}{2}+1\leq log_2(n) \leq h+1
h+2 \leq 2log_2(n) \leq 2h+2
=> Donc la hauteur de A est inférieure à 2\times log_2(n)
Preuve du lemme
Par réccurence sur la hauteur
Si h = 1, on suppose la propriété vrai jusqu’à h \leq n
Soit C un hauteur n+1 :
- Si n pair : n = 2k
- Les hauteurs complète A et B sont k
- La hauteur complète de C est k+1, or k+1 = 2k+1 = n+1
- Si n est impair : n = 2k+1
- …