Aller au contenu

TNSI : Arbres AVL
\(=\) Arbres Binaires de Recherche Équilibrés⚓︎

Définition⚓︎

Les deux inventeurs Adelson-Velskii 🇬🇧 et Landis 🇬🇧, ont étudié ces Arbres en \(1962\) dans leur article An Algorithm for the Organization of Information.

Arbre AVL, pour Adelson-Velskii et Landis, 1962

Un Arbre AVL est un Arbre Binaire de Recherche Équilibré, càd un ABR tel que, pour chaque noeud, les hauteurs des sous-arbres gauche (SAG) et sous-arbre droit (SAD) ne diffèrent au plus que de \(1\)

Caractérisation d'un Arbre AVL⚓︎

On peut traduire cette définition en calculant, pour chaque noeud, un paramètre/nombre nommé facteur d'équilibrage :

Facteur d'Équilibrage d'un noeud

Le facteur d'équilibrage \(eq(s)\) d'un noeud \(s\) est égal à la différence entre la hauteur du SAD de \(s\) et la hauteur du SAG de \(s\):

\(eq(s) = h_{SAD}-h_{SAG}\)

Caractérisation d'un Arbre AVL

Un ABR est un arbre AVL \(\Leftrightarrow\) tous les noeuds ont un facteur d'équilibrage de \(-1\), \(0\) ou \(1\)

Caractérisation d'un Arbre Déséquilibré

Un ABR est déséquilibré \(\Leftrightarrow\) il existe au moins un noeud tel que:

  • facteur \(\le -2\)
  • facteur \(\ge 2\)

Cas de Figure⚓︎

Arbres AVL⚓︎

ABR5050404050--40535350--53343440--34555540--55464653--46575753--57v134--v1383834--38494955--49606055--60v346--v3474746--47v260--v2656560--65

Arbre AVL

Un Exemple d'Arbres AVL : Les Arbres de Fibonacci : \(AF_{n+1}=1+AF_{n}+AF_{n-1}\)⚓︎

Principe Général Pour créer un nouvel arbre \(AF_{n+1}\), à partir de la connaissance des deux précédents:

  • On ajoute un nouveau noeud \(r\) à la Racine
  • L'enfant gauche de \(r\) est \(AF_{n}\)
  • L'enfant droit de \(r\) est \(AF_{n-1}\)

ABRcluster01AF_{n+1}rrAF_{n}AF_{n}r--AF_{n}AF_{n-1}AF_{n-1}r--AF_{n-1}

$$AF_{n+1}$$

Exemple des Premiers Arbres de Fibonacci

ABR11
AF1
ABR11221--2331--3
AF2
ABR11221--2331--3442--4552--5
AF3
ABR11221--2331--3v12--v1442--4552--5663--6773--7v23--v2884--8994--9
AF4
ABR11221--2331--3v12--v1442--4552--5663--6773--7v23--v2v34--v3884--8994--910105--1011115--11v45--v412126--1213136--1314148--1415158--15
AF5
ABR11221--2331--3v12--v1442--4552--5663--6773--7v23--v2v34--v3884--8994--910105--1011115--11v45--v412126--1213136--1314147--1415157--1516168--1617178--1718189--1819199--19202010--20212110--21v511--v5v611--v6242416--24252516--25222212--22232312--23
AF6
ABR5050181850--18707050--70121218--12242418--24565670--56v470--v4v112--v1161612--16191924--19v224--v2141416--14v316--v3v556--v5656556--65626265--62v665--v6
un ABR Non équilibré,
AVANT Rééquilibrage
$$\Rightarrow$$
ABR5050181850--18656550--65141418--14242418--24565665--56707065--70v114--v1121214--12161614--16191924--19v224--v2v312--v3v556--v5626256--62v4
un arbre AVL
= un ABR équilibré,
APRÈS Rééquilibrage

Hauteur Logarithmique d'un Arbre AVL⚓︎

Pte

Dans un arbre AVL, La hauteur \(h\) est logarithmique en \(n\) càd que \(h\) est proportionnelle à \(\log_2 (n)\,\,\) avec \(C\approx 1,45\) càd qu'il existe une constante \(C\) telle que : \(h \le C\times \log_2 (n)\)\(\,\,\,\) avec \(C\approx 1,45\)

Opérations de Base des Arbres AVL⚓︎

Recherche dans un Arbre AVL⚓︎

Recherche d'une Clé dans un Arbre AVL

La Recherche d'une Clé dans un arbre AVL se déroule exactement comme dans un Arbre Binaire de Recherche (ABR),

La complexité de la Recherche d'une Clé dans un Arbre AVL est donc encore en \(O(h)\), comme pour un arbre ABR, et de plus, puisque la hauteur \(h\) d'un arbre AVL est en \(O ( \log_2 ⁡ ( n ) )\), Alors :

Complexité de la Recherche dans un Arbre AVL

Dans un Arbre AVL, La Recherche d'une Clé se fait en \(O ( \log_2 ⁡ ( n ) )\)

Remarque La Recherche d'une Clé ne modifie pas la structure de l'arbre AVL

Insertion dans un Arbre AVL⚓︎

Principe Général de l'insertion dans un Arbre AVL⚓︎

Insertion d'une Clé dans un Arbre AVL

L'Insertion d'un noeud dans un arbre AVL se déroule en deux étapes :
1⃣ Insertion dans l'arbre AVL : Tout d'abord, on insère le noeud à la bonne place, exactement comme dans un ABR
2⃣ Rééquilibrage (si besoin) : Si le facteur d'équilibrage \(eq(s)\) d'un noeud \(s\) est : \(\le -2\) \(\,\) ou \(\ge 2\)
Alors on rééquilibre l'arbre AVL en remontant (uniquement) sur le chemin vers la racine depuis le noeud inséré en effectuant : * une Rotation Simple : complexité en \(O(1)\), ou bien * une Rotation Double (= \(2\) rotations simples connexes) : complexité en \(O(1)\)

Pour chaque insertion, il sera nécessaire de réaliser \(0\) ou \(1\) rotation simple ou double.

Rééquilibrage d'un Arbre AVL : Rotation Simple et Rotations Double⚓︎

Hein ❓ 😨 des Rotations ❓ C'est quoi çà ❓

Rotations Simples Une Rotation Simple (Gauche ou Droite) se réalise en temps constant : en \(O(1)\)

ROTzzqqz--qppq--pCCq--CAAp--ABBp--B
$$\xrightarrow[]{\text{Rotation Droite autour de q}}$$ $$\xleftarrow[\text{Rotation Gauche autour de p}]{}$$
ROTzzppz--pAAp--Aqqp--qBBq--BCCq--C

Rotations Doubles

  • Rotation Double à Droite autour de r : \(=\) Rotation Gauche-Droite
ROTzzrrz--rppr--pDDr--DAAp--Aqqp--qBBq--BCCq--C
$$\xrightarrow[]{\text{Rotation Gauche autour de p}}$$
ROTzzrrz--rqqr--qDDr--Dppq--pCCq--CAAp--ABBp--B
$$\xrightarrow[]{\text{Rotation Droite autour de r}}$$
ROTzqqz--qppq--prrq--r0p--0AAp--ABBp--BCCr--CDDr--D
  • Rotation Double à Gauche autour de r \(=\) Rotation Droite-Gauche
ROTzrrz--rDDr--Dppr--pqqp--qAAp--ACCq--CBBq--B
$$\xrightarrow[]{\text{Rotation Droite autour de p}}$$
ROTzrrz--rDDr--Dqqr--qCCq--Cppq--pBBp--BAAp--A
$$\xrightarrow[]{\text{Rotation Gauche autour de r}}$$
ROTzqqz--qrrq--rppq--pDDr--DCCr--C0p--0BBp--BAAp--A

Un Vrai Exemple détaillé d'insertion dans un AVL⚓︎

On considère l'arbre AVL suivant:

AVL10108810--8202010--20668--6v18--v1181820--18232320--23v223--v2252523--25

1⃣ Rotation Simple Droite \(\Leftrightarrow\) Facteurs d'Equilibrage \((-1;-2)\) \(\Rightarrow\) Exemple de l'Insertion de \(5\)

AVL1010088-210->8<1010->82020+110->2066-18->6<88->6v18->v11818020->182323+120->235506->5<66->5v36->v3v218->v2v423->v42525023->25
Après Insertion de 5,
L'Arbre AVL devient
provisoirement déséquilibré :
$$eq(6)=-1; eq(8)=-2$$
$$\xrightarrow[eq(6)=-1; \,\, eq(8)=-2]{\text{Rotation Droite autour de 6}}$$
AVL1010+166010--62020+110--205506--58806--81818020--182323+120--23v423--v42525023--25v1v2v3
Après Rééquilibrage par Rotation Droite,
L'Arbre AVL redevient équilibré.
TOUS les facteurs d'équilibrage vérifient :
$$eq(s)\in \{-1;0;+1\}$$

2⃣ Rotation Simple Gauche : Facteurs d'Equilibrage \((+1;+2)\) \(\Rightarrow\) Exemple de l'Insertion de \(27\)

AVL1010+288-110->82020+210->2010->20>106608->6v18->v11818020->182323+220->2320->23>20v36->v3v218->v2v423->v42525+123->2523->25>23v525->v52727025->2725->27>25
Après Insertion de 27,
L'Arbre AVL devient
provisoirement déséquilibré :
$$eq(25)=+1; \,\, eq(23)=+2$$
$$\xrightarrow[eq(25)=+1; \,\, eq(23)=+2]{\text{Rotation Gauche autour de 23}}$$
AVL1010+188-110--82020+110--206608--6v18--v11818020--182525020--252323025--232727025--27v2v3v4v5
Après Rééquilibrage par Rotation Gauche,
L'Arbre AVL redevient équilibré.
TOUS les facteurs d'équilibrage vérifient :
$$eq(s)\in \{-1;0;+1\}$$

3⃣ Rotation Double Droite : Facteurs d'Equilibrage \((+1;-2)\) \(\Rightarrow\) Exemple de l'Insertion de \(7\)

AVL1010088-210->8<1010->82020+110->2066+18->6<88->6v18->v11818020->182323+120->23v36->v37706->7>66->7v218->v2v423->v42525023->25
Après Insertion de 7,
L'Arbre AVL devient
provisoirement déséquilibré :
$$eq(6)=+1; \,\, eq(8)=-2$$
$$\xrightarrow[eq(6)=+1; \,\, eq(8)=-2]{\text{Rotation Double Droite autour de 8}}$$
AVL1010+177010--72020+110--206607--68807--81818020--182323+120--23v423--v42525023--25v1v2v3
Après Rééquilibrage par Rotation Double Droite,
L'Arbre AVL redevient équilibré.
TOUS les facteurs d'équilibrage vérifient :
$$eq(s)\in \{-1;0;+1\}$$

4⃣ Rotation Double Gauche : Facteurs d'Equilibrage \((-1;+2)\) \(\Rightarrow\) Exemple de l'Insertion de \(24\)

AVL1010+288-110->82020+210->2010->20>106608->6v18->v11818020->182323+220->2320->23>20v36->v3v218->v2v423->v42525-123->2523->25>232424025->2425->24<25v525->v5
Après Insertion de 24,
L'Arbre AVL devient
provisoirement déséquilibré :
$$eq(25)=-1; \,\, eq(23)=+2$$
$$\xrightarrow[eq(25)=-1; \,\, eq(23)=+2]{\text{Rotation Double Gauche autour de 23}}$$
AVL1010+188-110--82020+110--206608--6v18--v11818020--182424020--242323024--232525024--25v2v3v4v5
Après Rééquilibrage par Rotation Double Gauche,
L'Arbre AVL redevient équilibré.
TOUS les facteurs d'équilibrage vérifient :
$$eq(s)\in \{-1;0;+1\}$$

Complexité de l'Insertion d'une Clé dans un Arbre AVL⚓︎

La Complexité de l'Insertion d'une Clé dans un Arbre AVL est donc encore, dans le pire des cas, en \(O(h)+O(1)=O(h)\), et puisque la hauteur \(h\) d'un arbre AVL est en \(O ( \log_2 ⁡ ( n ) )\), Alors :

Complexité de l'Insertion d'une Clé dans un Arbre AVL

Dans un Arbre AVL, L'insertion d'une Clé se fait en \(O(\log_2 ⁡ (n))\) \(\,\) :

  • Chercher l'endroit où insérer la clé prend un temps \(O(\log_2 (n))\)
  • Trouver un noeud déséquilibré (s'il y en a un) prend un temps \(O(\log_2 (n))\)
  • Rééquilibrer l'arbre prend un temps \(O(1)\)

Suppression dans un Arbre AVL⚓︎

Suppression d'une Clé dans un Arbre AVL

La Suppression d'un noeud dans un arbre AVL se déroule en deux étapes :
1⃣ Suppression dans l'arbre AVL : Tout d'abord, on Supprime le noeud, exactement comme dans un ABR
2⃣ Rééquilibrage (si besoin) : Si le facteur d'équilibrage \(eq(s)\) d'un noeud \(s\) est : \(\le -2\) \(\,\) ou \(\ge 2\)
Alors on rééquilibre l'arbre AVL en remontant (uniquement) sur le chemin vers la racine depuis le noeud supprimé en effectuant :

  • une Rotation Simple : complexité en \(O(1)\), ou bien
  • une Rotation Double (= \(2\) rotations simples connexes) : complexité en \(O(1)\)

Pour chaque suppression, il sera nécessaire de réaliser au total entre \(0\) et \(h\) rotations simples ou doubles, où \(h\) est la hauteur (initiale) de l'arbre.

Complexité de la Suppression d'une Clé dans un Arbre AVL

La suppression se fait aussi en \(O ( \log_2 ⁡ ( n ) )\) \(\,\) :

  • Chercher le noeud à supprimer prend un temps \(O(\log_2 (n))\)
  • On devra faire, au plus, \(O(\log_2 (n))\) Rééquilibrages
  • Chaque Rééquilibrage prend un temps \(O(1)\)

Résumé des Opérations dans un Arbre AVL⚓︎

Pte

Dans un Arbre AVL, dans le pire des cas, on peut déterminer les complexités en temps pour les opérations suivantes :

  • Recherche d'une Clé : \(O(\log_2 (n))\)
  • Insertion d'une Clé : \(O(\log_2 (n))\)
  • Suppression d'une Clé : \(O(\log_2 (n))\)