ARBRE AVL (STRUCTURES DE DONNÉES)

L'arbre AVL est inventé par GM Adelson-Velsky et EM Landis en 1962. L'arbre est nommé AVL en l'honneur de ses inventeurs.

L'arbre AVL peut être défini comme un arbre de recherche binaire équilibré en hauteur dans lequel chaque nœud est associé à un facteur d'équilibre qui est calculé en soustrayant la hauteur de son sous-arbre droit de celle de son sous-arbre gauche.

L'arbre est dit équilibré si le facteur d'équilibre de chaque nœud est compris entre -1 et 1, sinon l'arbre sera déséquilibré et devra être équilibré.

Facteur d'équilibre (k) = hauteur (gauche(k)) - hauteur (droite(k))

Si le facteur d'équilibre d'un nœud est de 1, cela signifie que le sous-arbre de gauche est un niveau plus haut que le sous-arbre de droite.

Si le facteur d'équilibre d'un nœud est 0, cela signifie que le sous-arbre gauche et le sous-arbre droit ont la même hauteur.

Si le facteur d'équilibre d'un nœud est -1, cela signifie que le sous-arbre de gauche est un niveau inférieur au sous-arbre de droite.

Un arbre AVL est donné dans la figure suivante. Nous pouvons voir que le facteur d'équilibre associé à chaque nœud est compris entre -1 et +1. il s’agit donc d’un exemple d’arborescence AVL.

Complexité

Algorithme	Cas moyen	Pire cas
Espace	sur)	sur)
Recherche	o(log n)	o(log n)
Insérer	o(log n)	o(log n)
Supprimer	o(log n)	o(log n)

Opérations sur l'arborescence AVL

Étant donné que l'arbre AVL est également un arbre de recherche binaire, toutes les opérations sont effectuées de la même manière que dans un arbre de recherche binaire. La recherche et le parcours n'entraînent pas la violation des propriétés de l'arborescence AVL. Cependant, l'insertion et la suppression sont des opérations qui peuvent violer cette propriété et doivent donc être revues.

SN	Opération	Description
1	Insertion	L'insertion dans l'arborescence AVL s'effectue de la même manière que dans un arbre de recherche binaire. Cependant, cela peut entraîner une violation des propriétés de l'arborescence AVL et l'arborescence peut donc nécessiter un équilibrage. L'arbre peut être équilibré en appliquant des rotations.
2	Effacement	La suppression peut également être effectuée de la même manière que dans un arbre de recherche binaire. La suppression peut également perturber l'équilibre de l'arbre, c'est pourquoi différents types de rotations sont utilisés pour rééquilibrer l'arbre.

Pourquoi l'arbre AVL ?

L'arbre AVL contrôle la hauteur de l'arbre de recherche binaire en l'empêchant d'être biaisé. Le temps nécessaire pour toutes les opérations dans un arbre de recherche binaire de hauteur h est Oh) . Toutefois, il peut être étendu à Sur) si le BST devient asymétrique (c'est-à-dire le pire des cas). En limitant cette hauteur à log n, l'arbre AVL impose une borne supérieure à chaque opération à réaliser. O (log n) où n est le nombre de nœuds.

Rotations AVL

Nous effectuons une rotation dans l'arborescence AVL uniquement dans le cas où le facteur d'équilibre est autre que -1, 0 et 1 . Il existe essentiellement quatre types de rotations qui sont les suivantes :

Rotation L L : le nœud inséré se trouve dans le sous-arbre gauche du sous-arbre gauche de A
Rotation R R : le nœud inséré est dans le sous-arbre droit du sous-arbre droit de A
Rotation L R : le nœud inséré est dans le sous-arbre droit du sous-arbre gauche de A
Rotation R L : le nœud inséré est dans le sous-arbre gauche du sous-arbre droit de A

Où le nœud A est le nœud dont le facteur d'équilibre est différent de -1, 0, 1.

Les deux premières rotations LL et RR sont des rotations simples et les deux rotations suivantes LR et RL sont des rotations doubles. Pour qu'un arbre soit déséquilibré, la hauteur minimale doit être d'au moins 2, comprenons chaque rotation

1. Rotation RR

Lorsque BST devient déséquilibré, car un nœud est inséré dans le sous-arbre droit du sous-arbre droit de A, nous effectuons alors une rotation RR, la rotation RR est une rotation dans le sens inverse des aiguilles d'une montre, qui est appliquée sur le bord situé en dessous d'un nœud ayant un facteur d'équilibre -2.

Dans l'exemple ci-dessus, le nœud A a un facteur d'équilibre de -2 car un nœud C est inséré dans le sous-arbre droit du sous-arbre droit A. On effectue la rotation RR sur l’arête en dessous de A.

2. Rotation LL

Lorsque BST devient déséquilibré, car un nœud est inséré dans le sous-arbre gauche du sous-arbre gauche de C, nous effectuons alors une rotation LL, la rotation LL est une rotation dans le sens des aiguilles d'une montre, qui est appliquée sur le bord situé en dessous d'un nœud ayant un facteur d'équilibre de 2.

Dans l'exemple ci-dessus, le nœud C a un facteur d'équilibre de 2 car un nœud A est inséré dans le sous-arbre gauche du sous-arbre gauche C. Nous effectuons la rotation LL sur l’arête en dessous de A.

3. Rotation LR

Les doubles rotations sont un peu plus difficiles que les rotations simples déjà expliquées ci-dessus. Rotation LR = rotation RR + rotation LL, c'est-à-dire que la première rotation RR est effectuée sur le sous-arbre, puis la rotation LL est effectuée sur l'arbre complet, par arbre complet, nous entendons le premier nœud du chemin du nœud inséré dont le facteur d'équilibre est différent de -1 , 0 ou 1.

Comprenons très clairement chaque étape :

runes en PowerShell

État	Action
	Un nœud B a été inséré dans le sous-arbre droit de A le sous-arbre gauche de C, à cause de quoi C est devenu un nœud déséquilibré ayant un facteur d'équilibre de 2. Ce cas est une rotation L R où : Le nœud inséré est dans le sous-arbre droit du sous-arbre gauche de C
	Comme rotation LR = rotation RR + LL, donc RR (dans le sens inverse des aiguilles d'une montre) sur le sous-arbre enraciné en A est effectué en premier. En effectuant une rotation RR, le nœud UN , est devenu le sous-arbre gauche de B .
	Après avoir effectué la rotation RR, le nœud C est toujours déséquilibré, c'est-à-dire qu'il a un facteur d'équilibre de 2, car le nœud A inséré est à gauche de gauche de C
	Maintenant, nous effectuons une rotation LL dans le sens des aiguilles d'une montre sur l'arbre complet, c'est-à-dire sur le nœud C. C est maintenant devenu le sous-arbre droit du nœud B, A est le sous-arbre gauche de B
	Le facteur d'équilibre de chaque nœud est désormais de -1, 0 ou 1, c'est-à-dire que BST est désormais équilibré.

4. Rotation RL

Comme déjà mentionné, les doubles rotations sont un peu plus difficiles que les rotations simples déjà expliquées ci-dessus. Rotation R L = rotation LL + rotation RR, c'est-à-dire que la première rotation LL est effectuée sur le sous-arbre, puis la rotation RR est effectuée sur l'arbre complet, par arbre complet, nous entendons le premier nœud du chemin du nœud inséré dont le facteur d'équilibre est différent de -1 , 0 ou 1.

État	Action
	Un nœud B a été inséré dans le sous-arbre gauche de C le sous-arbre droit de UN , à cause de quoi A est devenu un nœud déséquilibré ayant un facteur d'équilibre de - 2. Ce cas est une rotation RL où : Le nœud inséré se trouve dans le sous-arbre gauche du sous-arbre droit de A.
	Comme rotation RL = rotation LL + rotation RR, donc LL (dans le sens des aiguilles d'une montre) sur le sous-arbre enraciné à C est effectué en premier. En effectuant une rotation RR, le nœud C est devenu le bon sous-arbre de B .
	Après avoir effectué la rotation LL, le nœud UN est toujours déséquilibré, c'est-à-dire qu'il a un facteur d'équilibre de -2, ce qui est dû au sous-arbre droit du nœud de sous-arbre droit A.
	Maintenant, nous effectuons une rotation RR (rotation dans le sens inverse des aiguilles d'une montre) sur l'arbre complet, c'est-à-dire sur le nœud A. C est maintenant devenu le sous-arbre droit du nœud B, et le nœud A est devenu le sous-arbre gauche de B.
	Le facteur d'équilibre de chaque nœud est désormais de -1, 0 ou 1, c'est-à-dire que BST est désormais équilibré.

Q : Construisez un arbre AVL contenant les éléments suivants

H, I, J, B, A, E, C, F, D, G, K, L

1. Insérez H, I, J

Lors de l'insertion des éléments ci-dessus, notamment dans le cas de H, le BST devient déséquilibré car le facteur d'équilibre de H est de -2. Puisque le BST est asymétrique à droite, nous effectuerons une rotation RR sur le nœud H.

L’arbre d’équilibre résultant est :

2. Insérez B, A

Lors de l'insertion des éléments ci-dessus, en particulier dans le cas de A, le BST devient déséquilibré car le facteur d'équilibre de H et I est de 2, nous considérons le premier nœud du dernier nœud inséré, c'est-à-dire H. Puisque le BST de H est asymétrique à gauche, nous effectuerons une rotation LL sur le nœud H.

L’arbre d’équilibre résultant est :

3. Insérez E

Lors de l'insertion de E, BST devient déséquilibré car le facteur d'équilibre de I est de 2, car si nous voyageons de E à I nous constatons qu'il est inséré dans le sous-arbre gauche du sous-arbre droit de I, nous effectuerons une rotation LR sur le nœud I. LR = rotation RR + LL

3 a) Nous effectuons d'abord la rotation RR sur le nœud B

L’arbre résultant après rotation RR est :

3b) On effectue d'abord une rotation LL sur le nœud I

L’arbre équilibré résultant après rotation LL est :

4. Insérez C, F, D

Lors de l'insertion de C, F, D, BST devient déséquilibré car le facteur d'équilibre de B et H est de -2, puisque si nous voyageons de D à B nous constatons qu'il est inséré dans le sous-arbre droit du sous-arbre gauche de B, nous effectuerons Rotation RL sur le nœud I. RL = rotation LL + RR.

4a) Nous effectuons d'abord la rotation LL sur le nœud E

L’arbre résultant après rotation LL est :

4b) On effectue ensuite une rotation RR sur le nœud B

L’arbre équilibré résultant après rotation RR est :

5. Insérez G

Lors de l'insertion de G, BST devient déséquilibré car le facteur d'équilibre de H est de 2, puisque si nous voyageons de G à H, nous constatons qu'il est inséré dans le sous-arbre gauche du sous-arbre droit de H, nous effectuerons une rotation LR sur le nœud I. Rotation LR = RR + LL.

télécharger des vidéos YouTube avec VLC

5 a) Nous effectuons d'abord la rotation RR sur le nœud C

L’arbre résultant après rotation RR est :

5 b) On effectue ensuite une rotation LL sur le nœud H

L’arbre équilibré résultant après rotation LL est :

6. Insérez K

Lors de l'insertion de K, BST devient déséquilibré car le facteur d'équilibre de I est de -2. Puisque le BST est asymétrique à droite de I à K, nous effectuerons donc une rotation RR sur le nœud I.