Alberi AVL: rotazioni, inserimento, eliminazione con C++ Esempio
Sara Chen
Cosa sono gli alberi AVL?
alberi AVL sono alberi di ricerca binari in cui la differenza tra l'altezza del sottoalbero sinistro e quello destro è -1, 0 o +1.
Gli alberi AVL sono anche chiamati alberi di ricerca binaria autobilancianti. Questi alberi aiutano a mantenere il tempo di ricerca logaritmico. Prende il nome dai suoi inventori (AVL) Adelson, Velsky e Landis.
Come funziona AVL Tree?
Per comprendere meglio la necessità degli alberi AVL, esaminiamo alcuni svantaggi dei semplici alberi di ricerca binari.
Consideriamo le seguenti chiavi inserite nell'ordine indicato nell'albero binario di ricerca.
L'altezza dell'albero cresce linearmente quando inseriamo le chiavi in ordine crescente del loro valore. Pertanto, l'operazione di ricerca, nel peggiore dei casi, richiede O(n).
La ricerca di un elemento richiede tempo lineare; quindi non è utile utilizzare il file Albero di ricerca binario struttura. D'altro canto, se l'altezza dell'albero è bilanciata, otteniamo un tempo di ricerca migliore.
Consideriamo ora le stesse chiavi ma inserite in un ordine diverso.
Qui le chiavi sono le stesse, ma poiché sono inserite in un ordine diverso, assumono posizioni diverse e l'altezza dell'albero rimane equilibrata. Quindi la ricerca non richiederà più di O(log n) per qualsiasi elemento dell'albero. È ormai evidente che se l'inserimento viene effettuato correttamente l'altezza dell'albero può essere mantenuta equilibrata.
Negli alberi AVL, teniamo sotto controllo l'altezza dell'albero durante l'operazione di inserimento. Vengono apportate modifiche per mantenere l'altezza bilanciata senza violare le proprietà fondamentali dell'albero di ricerca binario.
Fattore di equilibrio negli alberi AVL
Il fattore di equilibrio (BF) è un attributo fondamentale di ogni nodo negli alberi AVL che aiuta a monitorare l'altezza dell'albero.
Proprietà del fattore di equilibrio
- Il fattore di equilibrio è noto come differenza tra l'altezza del sottoalbero sinistro e del sottoalbero destro.
- Fattore di equilibrio(nodo) = altezza(nodo->sinistra) – altezza(nodo->destra)
- I valori consentiti di BF sono –1, 0 e +1.
- Il valore –1 indica che il sottoalbero destro ne contiene uno in più, cioè l'albero è pesante.
- Il valore +1 indica che il sottoalbero di sinistra ne contiene uno in più, cioè l'albero è lasciato pesante.
- Il valore 0 mostra che l'albero comprende nodi uguali su ciascun lato, cioè l'albero è perfettamente bilanciato.
Rotazioni AVL
Per far sì che l'AVL Tree stesso si equilibri, quando si inserisce o si elimina un nodo dall'albero vengono eseguite delle rotazioni.
Eseguiamo le seguenti rotazioni LL, RR, LR e RL.
- Sinistra – Rotazione sinistra
- Destra – Rotazione a destra
- Rotazione destra – sinistra
- Rotazione sinistra-destra
Sinistra – Rotazione sinistra
Questa rotazione viene eseguita quando un nuovo nodo viene inserito nel figlio sinistro del sottoalbero sinistro.
Viene eseguita una singola rotazione a destra. Questo tipo di rotazione viene identificato quando un nodo ha un fattore di equilibrio pari a +2 e il suo figlio sinistro ha un fattore di equilibrio pari a +1.
Destra – Rotazione a destra
Questa rotazione viene eseguita quando un nuovo nodo viene inserito nel figlio destro del sottoalbero destro.
Viene eseguita una singola rotazione a sinistra. Questo tipo di rotazione viene identificato quando un nodo ha un fattore di equilibrio pari a -2 e il suo figlio destro ha un fattore di equilibrio pari a -1.
Rotazione destra – sinistra
Questa rotazione viene eseguita quando un nuovo nodo viene inserito nel figlio destro del sottoalbero sinistro.
Questa rotazione viene eseguita quando un nodo ha un fattore di equilibrio pari a –2 e il suo figlio destro ha un fattore di equilibrio pari a +1.
Rotazione sinistra-destra
Questa rotazione viene eseguita quando un nuovo nodo viene inserito nel figlio sinistro del sottoalbero destro.
Questa rotazione viene eseguita quando un nodo ha un fattore di equilibrio pari a +2 e il suo figlio sinistro ha un fattore di equilibrio pari a -1.
Inserimento negli alberi AVL
L'operazione di inserimento è quasi la stessa degli alberi binari di ricerca semplici. Dopo ogni inserimento, bilanciamo l'altezza dell'albero. L'operazione di inserimento richiede O(log n) di complessità temporale peggiore.
Passo 1 : Inserisci il nodo nell'albero AVL utilizzando lo stesso algoritmo di inserimento di BST. Nell'esempio sopra, inserisci 160.
Passo 2 : Una volta aggiunto il nodo, il fattore di equilibrio di ciascun nodo viene aggiornato. Dopo aver inserito 160, il fattore di equilibrio di ogni nodo viene aggiornato.
Passo 3 : Ora controlla se qualche nodo viola l'intervallo del fattore di equilibrio se il fattore di equilibrio viene violato, quindi esegui le rotazioni utilizzando il caso seguente. Nell'esempio sopra, il fattore di equilibrio di 350 viene violato e il caso 1 diventa applicabile, eseguiamo la rotazione LL e l'albero viene nuovamente bilanciato.
- Se BF(nodo) = +2 e BF(nodo -> figlio sinistro) = +1, esegui la rotazione LL.
- Se BF(nodo) = -2 e BF(nodo -> figlio destro) = 1, esegui la rotazione RR.
- Se BF(nodo) = -2 e BF(nodo -> figlio destro) = +1, esegui la rotazione RL.
- Se BF(nodo) = +2 e BF(nodo -> figlio sinistro) = -1, esegui la rotazione LR.
Cancellazione negli alberi AVL
Anche la cancellazione è molto semplice. Eliminiamo utilizzando la stessa logica dei semplici alberi di ricerca binari. Dopo l'eliminazione, ristrutturiamo l'albero, se necessario, per mantenere la sua altezza equilibrata.
Passo 1: Trova l'elemento nell'albero.
Passo 2: Elimina il nodo, come da Eliminazione BST.
Passo 3: Sono possibili due casi: -
Caso 1: Eliminazione dal sottoalbero destro.
- 1A. Se BF(nodo) = +2 e BF(nodo -> figlio sinistro) = +1, esegui la rotazione LL.
- 1B. Se BF(nodo) = +2 e BF(nodo -> figlio sinistro) = -1, esegui la rotazione LR.
- 1C. Se BF(nodo) = +2 e BF(nodo -> figlio sinistro) = 0, esegui la rotazione LL.
Caso 2: Eliminazione dal sottoalbero sinistro.
- 2A. Se BF(nodo) = -2 e BF(nodo -> figlio destro) = -1, esegui la rotazione RR.
- 2B. Se BF(nodo) = -2 e BF(nodo -> figlio destro) = +1, esegui la rotazione RL.
- 2C. Se BF(nodo) = -2 e BF(nodo -> figlio destro) = 0, esegui la rotazione RR.
C++ Esempio di alberi AVL
Di seguito è il C++ che implementa gli alberi 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);
}
Esempio di esecuzione del codice sopra:
- Copia il codice sopra e incollalo in "avl.cpp".
- Compila il codice:
g++ avl.cpp -o run
- Esegui il codice.
./run
Vantaggi degli alberi AVL
- L'altezza dell'albero AVL è sempre equilibrata. L'altezza non supera mai il log N, dove N è il numero totale di nodi dell'albero.
- Rispetto ai semplici alberi di ricerca binaria, garantisce una migliore complessità dei tempi di ricerca.
- Gli alberi AVL hanno capacità di autobilanciamento.
Sommario
- Gli alberi AVL sono alberi di ricerca binari autobilanciati.
- Il fattore di equilibrio è l'attributo fondamentale degli alberi AVL
- Il fattore di equilibrio di un nodo è definito come la differenza tra l'altezza del sottoalbero sinistro e destro di quel nodo.
- I valori validi del fattore di equilibrio sono -1, 0 e +1.
- L'operazione di inserimento ed eliminazione richiede che le rotazioni vengano eseguite dopo aver violato il fattore di bilanciamento.
- La complessità temporale delle operazioni di inserimento, eliminazione e ricerca è O(log N).
- Gli alberi AVL seguono tutte le proprietà degli alberi di ricerca binaria.
- Il sottoalbero di sinistra ha nodi minori del nodo radice. Il sottoalbero destro ha nodi che sono sempre maggiori del nodo radice.
- Gli alberi AVL vengono utilizzati laddove le operazioni di ricerca sono più frequenti rispetto alle operazioni di inserimento ed eliminazione.
