Arbres AVL : rotations, insertion, suppression avec C++ Exemple
Sarah Chen
Que sont les arbres AVL ?
Arbres AVL sont des arbres de recherche binaires dans lesquels la différence entre la hauteur des sous-arbres gauche et droit est soit -1, 0 ou +1.
Les arbres AVL sont également appelés arbres de recherche binaires auto-équilibrés. Ces arbres aident à maintenir le temps de recherche logarithmique. Il porte le nom de ses inventeurs (AVL) Adelson, Velsky et Landis.
Comment fonctionne l’arbre AVL ?
Pour mieux comprendre la nécessité des arbres AVL, examinons quelques inconvénients des arbres de recherche binaires simples.
Considérez les clés suivantes insérées dans l'ordre donné dans l'arborescence de recherche binaire.
La hauteur de l’arbre augmente linéairement lorsque nous insérons les clés dans l’ordre croissant de leur valeur. Ainsi, l’opération de recherche prend, au pire, O(n).
Il faut un temps linéaire pour rechercher un élément ; il ne sert donc à rien d'utiliser le Arbre de recherche binaire structure. En revanche, si la hauteur de l’arbre est équilibrée, nous obtenons un meilleur temps de recherche.
Regardons maintenant les mêmes clés mais insérées dans un ordre différent.
Ici, les touches sont les mêmes, mais comme elles sont insérées dans un ordre différent, elles prennent des positions différentes, et la hauteur de l'arbre reste équilibrée. Par conséquent, la recherche ne prendra pas plus de O(log n) pour n’importe quel élément de l’arborescence. Il est désormais évident que si l'insertion est effectuée correctement, la hauteur de l'arbre peut rester équilibrée.
Dans les arbres AVL, nous contrôlons la hauteur de l'arbre pendant l'opération d'insertion. Des modifications sont apportées pour maintenir la hauteur équilibrée sans violer les propriétés fondamentales de l'arbre de recherche binaire.
Facteur d’équilibre dans les arbres AVL
Le facteur d'équilibre (BF) est un attribut fondamental de chaque nœud des arbres AVL qui permet de surveiller la hauteur de l'arbre.
Propriétés du facteur d'équilibre
- Le facteur d'équilibre est connu comme la différence entre la hauteur du sous-arbre gauche et du sous-arbre droit.
- Facteur d'équilibre (nœud) = hauteur (nœud-> gauche) – hauteur (nœud-> droite)
- Les valeurs autorisées de BF sont –1, 0 et +1.
- La valeur –1 indique que le sous-arbre de droite en contient un supplémentaire, c'est-à-dire que l'arbre est lourd à droite.
- La valeur +1 indique que le sous-arbre de gauche contient un extra, c'est-à-dire que l'arbre est laissé lourd.
- La valeur 0 montre que l'arbre comprend des nœuds égaux de chaque côté, c'est à dire que l'arbre est parfaitement équilibré.
Rotations AVL
Pour équilibrer l'arborescence AVL, lors de l'insertion ou de la suppression d'un nœud de l'arborescence, des rotations sont effectuées.
Nous effectuons les rotations LL, RR, LR et RL suivantes.
- Gauche – Rotation à gauche
- Droite – Rotation à droite
- Rotation droite – gauche
- Rotation gauche – droite
Gauche – Rotation à gauche
Cette rotation est effectuée lorsqu'un nouveau nœud est inséré au niveau de l'enfant gauche du sous-arbre gauche.
Une seule rotation à droite est effectuée. Ce type de rotation est identifié lorsqu'un nœud a un facteur d'équilibre de +2 et que son enfant gauche a un facteur d'équilibre de +1.
Droite – Rotation à droite
Cette rotation est effectuée lorsqu'un nouveau nœud est inséré au niveau de l'enfant droit du sous-arbre droit.
Une seule rotation vers la gauche est effectuée. Ce type de rotation est identifié lorsqu'un nœud a un facteur d'équilibre de -2 et que son enfant droit a un facteur d'équilibre de -1.
Rotation droite – gauche
Cette rotation est effectuée lorsqu'un nouveau nœud est inséré au niveau de l'enfant droit du sous-arbre gauche.
Cette rotation est effectuée lorsqu'un nœud a un facteur d'équilibre de -2 et que son enfant droit a un facteur d'équilibre de +1.
Rotation gauche – droite
Cette rotation est effectuée lorsqu'un nouveau nœud est inséré au niveau de l'enfant gauche du sous-arbre droit.
Cette rotation est effectuée lorsqu'un nœud a un facteur d'équilibre de +2 et que son enfant gauche a un facteur d'équilibre de -1.
Insertion dans les arbres AVL
L’opération d’insertion est presque la même que dans les arbres de recherche binaires simples. Après chaque insertion, nous équilibrons la hauteur de l'arbre. L’opération d’insertion prend la pire complexité temporelle O (log n).
Étape 1: Insérez le nœud dans l'arborescence AVL en utilisant le même algorithme d'insertion de BST. Dans l'exemple ci-dessus, insérez 160.
Étape 2: Une fois le nœud ajouté, le facteur d'équilibre de chaque nœud est mis à jour. Après l'insertion de 160, le facteur d'équilibre de chaque nœud est mis à jour.
Étape 3: Vérifiez maintenant si un nœud viole la plage du facteur d'équilibre si le facteur d'équilibre est violé, puis effectuez des rotations en utilisant le cas ci-dessous. Dans l'exemple ci-dessus, le facteur d'équilibre de 350 est violé et le cas 1 y devient applicable, nous effectuons une rotation LL et l'arbre est à nouveau équilibré.
- Si BF(node) = +2 et BF(node -> left-child) = +1, effectuez une rotation LL.
- Si BF(node) = -2 et BF(node -> right-child) = 1, effectuez une rotation RR.
- Si BF(node) = -2 et BF(node -> right-child) = +1, effectuez une rotation RL.
- Si BF(node) = +2 et BF(node -> left-child) = -1, effectuez une rotation LR.
Suppression dans les arborescences AVL
La suppression est également très simple. Nous supprimons en utilisant la même logique que dans les arbres de recherche binaires simples. Après suppression, nous restructurons l'arbre, si nécessaire, pour conserver sa hauteur équilibrée.
Étape 1 : Trouvez l'élément dans l'arborescence.
Étape 2 : Supprimez le nœud, conformément à la suppression BST.
Étape 3 : Deux cas sont possibles : -
1 cas: Suppression du sous-arbre droit.
- 1A. Si BF(node) = +2 et BF(node -> left-child) = +1, effectuez une rotation LL.
- 1B. Si BF(node) = +2 et BF(node -> left-child) = -1, effectuez une rotation LR.
- 1C. Si BF(node) = +2 et BF(node -> left-child) = 0, effectuez une rotation LL.
Cas 2: Suppression du sous-arbre gauche.
- 2A. Si BF(node) = -2 et BF(node -> right-child) = -1, effectuez une rotation RR.
- 2B. Si BF(node) = -2 et BF(node -> right-child) = +1, effectuez une rotation RL.
- 2C. Si BF(node) = -2 et BF(node -> right-child) = 0, effectuez une rotation RR.
C++ Exemple d'arbres AVL
Voici le C++ qui implémente les arborescences AVL :
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
struct node {
struct node *left;
int data;
int height;
struct node *right;
};
class AVL
{
private:
public:
struct node * root;
AVL(){
this->root = NULL;
}
int calheight(struct node *p){
if(p->left && p->right){
if (p->left->height < p->right->height)
return p->right->height + 1;
else return p->left->height + 1;
}
else if(p->left && p->right == NULL){
return p->left->height + 1;
}
else if(p->left ==NULL && p->right){
return p->right->height + 1;
}
return 0;
}
int bf(struct node *n){
if(n->left && n->right){
return n->left->height - n->right->height;
}
else if(n->left && n->right == NULL){
return n->left->height;
}
else if(n->left== NULL && n->right ){
return -n->right->height;
}
}
struct node * llrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->left;
p->left = tp->right;
tp->right = p;
return tp;
}
struct node * rrrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->right;
p->right = tp->left;
tp->left = p;
return tp;
}
struct node * rlrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->right;
tp2 =p->right->left;
p -> right = tp2->left;
tp ->left = tp2->right;
tp2 ->left = p;
tp2->right = tp;
return tp2;
}
struct node * lrrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->left;
tp2 =p->left->right;
p -> left = tp2->right;
tp ->right = tp2->left;
tp2 ->right = p;
tp2->left = tp;
return tp2;
}
struct node* insert(struct node *r,int data){
if(r==NULL){
struct node *n;
n = new struct node;
n->data = data;
r = n;
r->left = r->right = NULL;
r->height = 1;
return r;
}
else{
if(data < r->data)
r->left = insert(r->left,data);
else
r->right = insert(r->right,data);
}
r->height = calheight(r);
if(bf(r)==2 && bf(r->left)==1){
r = llrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==-1){
r = rrrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==1){
r = rlrotation(r);
}
else if(bf(r)==2 && bf(r->left)==-1){
r = lrrotation(r);
}
return r;
}
void levelorder_newline(){
if (this->root == NULL){
cout<<"\n"<<"Empty tree"<<"\n";
return;
}
levelorder_newline(this->root);
}
void levelorder_newline(struct node *v){
queue <struct node *> q;
struct node *cur;
q.push(v);
q.push(NULL);
while(!q.empty()){
cur = q.front();
q.pop();
if(cur == NULL && q.size()!=0){
cout<<"\n";
q.push(NULL);
continue;
}
if(cur!=NULL){
cout<<" "<<cur->data;
if (cur->left!=NULL){
q.push(cur->left);
}
if (cur->right!=NULL){
q.push(cur->right);
}
}
}
}
struct node * deleteNode(struct node *p,int data){
if(p->left == NULL && p->right == NULL){
if(p==this->root)
this->root = NULL;
delete p;
return NULL;
}
struct node *t;
struct node *q;
if(p->data < data){
p->right = deleteNode(p->right,data);
}
else if(p->data > data){
p->left = deleteNode(p->left,data);
}
else{
if(p->left != NULL){
q = inpre(p->left);
p->data = q->data;
p->left=deleteNode(p->left,q->data);
}
else{
q = insuc(p->right);
p->data = q->data;
p->right = deleteNode(p->right,q->data);
}
}
if(bf(p)==2 && bf(p->left)==1){ p = llrotation(p); }
else if(bf(p)==2 && bf(p->left)==-1){ p = lrrotation(p); }
else if(bf(p)==2 && bf(p->left)==0){ p = llrotation(p); }
else if(bf(p)==-2 && bf(p->right)==-1){ p = rrrotation(p); }
else if(bf(p)==-2 && bf(p->right)==1){ p = rlrotation(p); }
else if(bf(p)==-2 && bf(p->right)==0){ p = llrotation(p); }
return p;
}
struct node* inpre(struct node* p){
while(p->right!=NULL)
p = p->right;
return p;
}
struct node* insuc(struct node* p){
while(p->left!=NULL)
p = p->left;
return p;
}
~AVL(){
}
};
int main(){
AVL b;
int c,x;
do{
cout<<"\n1.Display levelorder on newline";
cout<<"\n2.Insert";
cout<<"\n3.Delete\n";
cout<<"\n0.Exit\n";
cout<<"\nChoice: ";
cin>>c;
switch (c)
{
case 1:
b.levelorder_newline();
// to print the tree in level order
break;
case 2:
cout<<"\nEnter no. ";
cin>>x;
b.root = b.insert(b.root,x);
break;
case 3:
cout<<"\nWhat to delete? ";
cin>>x;
b.root = b.deleteNode(b.root,x);
break;
case 0:
break;
}
} while(c!=0);
}
Exemple d'exécution du code ci-dessus :
- Copiez le code ci-dessus et collez-le dans « avl.cpp ».
- Compilez le code :
g++ avl.cpp -o run
- Exécutez le code.
./run
Avantages des arbres AVL
- La hauteur de l'arbre AVL est toujours équilibrée. La hauteur ne dépasse jamais log N, où N est le nombre total de nœuds dans l’arborescence.
- Il offre une meilleure complexité de temps de recherche par rapport aux simples arbres de recherche binaire.
- Les arbres AVL ont des capacités d’auto-équilibrage.
Résumé
- Les arbres AVL sont des arbres de recherche binaires auto-équilibrés.
- Le facteur d'équilibre est l'attribut fondamental des arbres AVL
- Le facteur d'équilibre d'un nœud est défini comme la différence entre la hauteur des sous-arbres gauche et droit de ce nœud.
- Les valeurs valides du facteur d'équilibre sont -1, 0 et +1.
- Les opérations d'insertion et de suppression nécessitent que des rotations soient effectuées après avoir violé le facteur d'équilibre.
- La complexité temporelle des opérations d'insertion, de suppression et de recherche est O (log N).
- Les arbres AVL suivent toutes les propriétés des arbres de recherche binaires.
- Le sous-arbre de gauche a des nœuds inférieurs au nœud racine. Le sous-arbre de droite a des nœuds toujours supérieurs au nœud racine.
- Les arborescences AVL sont utilisées lorsque les opérations de recherche sont plus fréquentes que les opérations d'insertion et de suppression.
