Chapitre 10 : Arbre Binaire de Recherche et arbre AVL
On veut implanter un « ensemble d’entiers »
Methode 1 : Tableau d’entiers
Complexité temps
- Ajout : \(O(1)\)
- Test de présence : \(O(n)\) -> avec \(n\) : taille de l’ensemble
Methode 2 : Arbre binaire de recherche
Complexité temps (pire des cas)
- Ajout : \(O(n)\)
- Test Présence : \(O(n)\)
Définition : (ABR : arbre binaire de recherche)
On dit qu’un arbre binaire étiqueté par des entiers est un arbre binaire de recherche si pour tout nœud V :
- Les etiquettes situées « a gauche » de V sont strictement inférieures à l’étiquette de V
- Les étiquettes situées « a droite » de V sont strictement supérieures à l’étiquette de V.
Illustration :
On ajoute dans cet ordre à un ABR les valeurs suivantes :
\(8 \;3\; 16\; 17\; 23\; 2\; 5\; 3\; 1\; 9\; 7\)
Pour ajouter une valeur on descend dans l’arbre jusqu’à trouver une place vide, à chaque nœud si la valeur à ajouter :
- Est inferieur -> gauche
- Est supérieur -> droite
- Est égale -> stop
Problème : Si l’arbre est « déséquilibré »
\(1\; 23\; 2\; 3\; 17\; 3\; 5\; 7\; 16\; 9\; 8\)
Idée : à chaque ajout (non retrait) on effectue des « rotations » (voir suite) pour « équilibrer » l’ABR.
Definition : arbre équilibré
Un arbre binaire est dit équilibré, soit :
- S’il est vide
- Soit les deux sous-arbres de la racine sont équilibrés et leur hauteur ne diffère que d’au plus 1.
Exemple :
Théorème :
La hauteur d’un arbre binaire équilibré de n nœud est inférieur à \(2 \times log_2(n)\)
(Idée : par récurrence on montre que dans un arbre équilibré de hauteur h, les nœuds de profondeur \(< h/2\) forment un arbre complet)
Definition : arbre AVL
On appelera AVL, un ABR qui est équilibré.
Rotation (sur un nœud)
Une rotation gauche ou droite conserve la structure d’ABR (en modifiant certaines hauteurs)
Comment utiliser les rotations pour rééquilibrer ?
Cas possible
Cas 2
Cas 3
Cas 1
Après chaque ajout ou retrait d’un élément, on verifie sur chaque nœud de la branche parcouru s’il est en déséquilibre. Si c’est le cas on rééquilibre avec une rotation ou une double rotation RotX(?) sur RotY(?)