Δέντρα AVL: Περιστροφές, Εισαγωγή, Διαγραφή με C++ Παράδειγμα
Σάρα Τσεν
Τι είναι τα AVL Trees;
AVL δέντρα είναι δυαδικά δέντρα αναζήτησης στα οποία η διαφορά μεταξύ του ύψους του αριστερού και του δεξιού υποδέντρου είναι -1, 0 ή +1.
Τα δέντρα AVL ονομάζονται επίσης αυτοεξισορροπούμενο δυαδικό δέντρο αναζήτησης. Αυτά τα δέντρα βοηθούν στη διατήρηση του λογαριθμικού χρόνου αναζήτησης. Πήρε το όνομά του από τους εφευρέτες του (AVL) Adelson, Velsky και Landis.
Πώς λειτουργεί το AVL Tree;
Για να κατανοήσουμε καλύτερα την ανάγκη για δέντρα AVL, ας δούμε μερικά μειονεκτήματα των απλών δυαδικών δέντρων αναζήτησης.
Εξετάστε τα ακόλουθα κλειδιά που έχουν εισαχθεί με τη δεδομένη σειρά στο δέντρο δυαδικής αναζήτησης.
Το ύψος του δέντρου μεγαλώνει γραμμικά σε μέγεθος όταν εισάγουμε τα κλειδιά με αύξουσα σειρά της αξίας τους. Έτσι, η λειτουργία αναζήτησης, στη χειρότερη περίπτωση, παίρνει O(n).
Χρειάζεται γραμμικός χρόνος για την αναζήτηση ενός στοιχείου. ως εκ τούτου δεν υπάρχει καμία χρήση της χρήσης του Δυαδικό δέντρο αναζήτησης δομή. Από την άλλη, αν το ύψος του δέντρου είναι ισορροπημένο, έχουμε καλύτερο χρόνο αναζήτησης.
Ας δούμε τώρα τα ίδια πλήκτρα αλλά εισάγονται με διαφορετική σειρά.
Εδώ, τα πλήκτρα είναι τα ίδια, αλλά επειδή εισάγονται με διαφορετική σειρά, παίρνουν διαφορετικές θέσεις και το ύψος του δέντρου παραμένει ισορροπημένο. Ως εκ τούτου, η αναζήτηση δεν θα διαρκέσει περισσότερο από το O(log n) για οποιοδήποτε στοιχείο του δέντρου. Είναι πλέον προφανές ότι εάν η εισαγωγή γίνει σωστά, το ύψος του δέντρου μπορεί να διατηρηθεί ισορροπημένο.
Στα δέντρα AVL, ελέγχουμε το ύψος του δέντρου κατά τη λειτουργία εισαγωγής. Γίνονται τροποποιήσεις για να διατηρηθεί το ισορροπημένο ύψος χωρίς να παραβιάζονται οι θεμελιώδεις ιδιότητες του Δυαδικού Δέντρου αναζήτησης.
Συντελεστής ισορροπίας στα δέντρα AVL
Ο συντελεστής ισορροπίας (BF) είναι ένα θεμελιώδες χαρακτηριστικό κάθε κόμβου στα δέντρα AVL που βοηθά στην παρακολούθηση του ύψους του δέντρου.
Ιδιότητες του Συντελεστή Ισοζυγίου
- Ο παράγοντας ισορροπίας είναι γνωστός ως η διαφορά μεταξύ του ύψους του αριστερού υποδέντρου και του δεξιού υποδέντρου.
- Συντελεστής ισορροπίας(κόμβος) = ύψος(κόμβος->αριστερά) – ύψος(κόμβος->δεξιά)
- Οι επιτρεπόμενες τιμές του BF είναι –1, 0 και +1.
- Η τιμή –1 υποδηλώνει ότι το δεξί υποδέντρο περιέχει ένα επιπλέον, δηλαδή, το δέντρο είναι σωστά βαρύ.
- Η τιμή +1 υποδεικνύει ότι το αριστερό υποδέντρο περιέχει ένα επιπλέον, δηλαδή, το δέντρο παραμένει βαρύ.
- Η τιμή 0 δείχνει ότι το δέντρο περιλαμβάνει ίσους κόμβους σε κάθε πλευρά, δηλαδή, το δέντρο είναι τέλεια ισορροπημένο.
Περιστροφές AVL
Για να εξισορροπηθεί το ίδιο το δέντρο AVL, κατά την εισαγωγή ή τη διαγραφή ενός κόμβου από το δέντρο, εκτελούνται περιστροφές.
Εκτελούμε την ακόλουθη περιστροφή LL, περιστροφή RR, περιστροφή LR και περιστροφή RL.
- Αριστερά – Αριστερή Περιστροφή
- Δεξιά – Δεξιά περιστροφή
- Δεξιά – Αριστερά Περιστροφή
- Περιστροφή Αριστερά – Δεξιά
Αριστερά – Αριστερή Περιστροφή
Αυτή η περιστροφή πραγματοποιείται όταν εισάγεται ένας νέος κόμβος στο αριστερό παιδί του αριστερού υποδέντρου.
Εκτελείται μία μόνο δεξιά περιστροφή. Αυτός ο τύπος περιστροφής προσδιορίζεται όταν ένας κόμβος έχει ισορροπημένο παράγοντα ως +2 και το αριστερό παιδί του έχει έναν παράγοντα ισορροπίας ως +1.
Δεξιά – Δεξιά περιστροφή
Αυτή η περιστροφή πραγματοποιείται όταν εισάγεται ένας νέος κόμβος στο δεξί παιδί του δεξιού υποδέντρου.
Εκτελείται μία μόνο περιστροφή αριστερά. Αυτός ο τύπος περιστροφής προσδιορίζεται όταν ένας κόμβος έχει έναν ισορροπημένο παράγοντα ως -2 και το δεξιό παιδί του έχει έναν παράγοντα ισορροπίας ως -1.
Δεξιά – Αριστερά Περιστροφή
Αυτή η περιστροφή πραγματοποιείται όταν εισάγεται ένας νέος κόμβος στο δεξί παιδί του αριστερού υποδέντρου.
Αυτή η περιστροφή εκτελείται όταν ένας κόμβος έχει συντελεστή ισορροπίας ως –2 και το δεξιό παιδί του έχει συντελεστή ισορροπίας ως +1.
Περιστροφή Αριστερά – Δεξιά
Αυτή η περιστροφή πραγματοποιείται όταν εισάγεται ένας νέος κόμβος στο αριστερό παιδί του δεξιού υποδέντρου.
Αυτή η περιστροφή εκτελείται όταν ένας κόμβος έχει συντελεστή ισορροπίας +2 και το αριστερό παιδί του έχει συντελεστή ισορροπίας ως -1.
Εισαγωγή σε δέντρα AVL
Η λειτουργία εισαγωγής είναι σχεδόν η ίδια όπως στα απλά δυαδικά δέντρα αναζήτησης. Μετά από κάθε εισαγωγή, ισορροπούμε το ύψος του δέντρου. Η λειτουργία εισαγωγής απαιτεί O(log n) χειρότερο χρόνο πολυπλοκότητας.
Βήμα 1: Εισαγάγετε τον κόμβο στο δέντρο AVL χρησιμοποιώντας τον ίδιο αλγόριθμο εισαγωγής του BST. Στο παραπάνω παράδειγμα, εισαγάγετε 160.
Βήμα 2: Μόλις προστεθεί ο κόμβος, ενημερώνεται ο παράγοντας ισορροπίας κάθε κόμβου. Αφού εισαχθεί το 160, ενημερώνεται ο παράγοντας ισορροπίας κάθε κόμβου.
Βήμα 3: Τώρα ελέγξτε εάν κάποιος κόμβος παραβιάζει το εύρος του συντελεστή ισορροπίας εάν παραβιαστεί ο παράγοντας ισορροπίας και, στη συνέχεια, πραγματοποιήστε περιστροφές χρησιμοποιώντας την παρακάτω περίπτωση. Στο παραπάνω παράδειγμα, ο συντελεστής ισορροπίας 350 παραβιάζεται και η περίπτωση 1 εφαρμόζεται εκεί, εκτελούμε περιστροφή LL και το δέντρο ισορροπεί ξανά.
- Εάν BF(κόμβος) = +2 και BF(κόμβος -> αριστερό παιδί) = +1, εκτελέστε περιστροφή LL.
- Εάν BF(κόμβος) = -2 και BF(κόμβος -> δεξιό παιδί) = 1, εκτελέστε περιστροφή RR.
- Εάν BF(κόμβος) = -2 και BF(κόμβος -> δεξιό παιδί) = +1, εκτελέστε περιστροφή RL.
- Εάν BF(κόμβος) = +2 και BF(κόμβος -> αριστερό παιδί) = -1, εκτελέστε περιστροφή LR.
Διαγραφή σε AVL Trees
Η διαγραφή είναι επίσης πολύ απλή. Διαγράφουμε χρησιμοποιώντας την ίδια λογική όπως στα απλά δυαδικά δέντρα αναζήτησης. Μετά τη διαγραφή, αναδομούμε το δέντρο, εάν χρειάζεται, για να διατηρήσει το ισορροπημένο ύψος του.
Βήμα 1: Βρείτε το στοιχείο στο δέντρο.
Βήμα 2: Διαγράψτε τον κόμβο, σύμφωνα με τη Διαγραφή BST.
Βήμα 3: Δύο περιπτώσεις είναι δυνατές: -
Υπόθεση 1: Διαγραφή από το δεξί υποδέντρο.
- 1Α. Εάν BF(κόμβος) = +2 και BF(κόμβος -> αριστερό παιδί) = +1, εκτελέστε περιστροφή LL.
- 1Β. Εάν BF(κόμβος) = +2 και BF(κόμβος -> αριστερό παιδί) = -1, εκτελέστε περιστροφή LR.
- 1C. Εάν BF(κόμβος) = +2 και BF(κόμβος -> αριστερό παιδί) = 0, εκτελέστε περιστροφή LL.
Υπόθεση 2: Διαγραφή από το αριστερό υποδέντρο.
- 2Α. Εάν BF(κόμβος) = -2 και BF(κόμβος -> δεξιό παιδί) = -1, εκτελέστε περιστροφή RR.
- 2Β. Εάν BF(κόμβος) = -2 και BF(κόμβος -> δεξιό παιδί) = +1, εκτελέστε περιστροφή RL.
- 2C. Εάν BF(κόμβος) = -2 και BF(κόμβος -> δεξιό παιδί) = 0, εκτελέστε περιστροφή RR.
C++ Παράδειγμα AVL Trees
Παρακάτω είναι το C++ που υλοποιεί δέντρα 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);
}
Παράδειγμα εκτέλεσης του παραπάνω κώδικα:
- Αντιγράψτε τον παραπάνω κώδικα και επικολλήστε στο "avl.cpp".
- Μεταγλωττίστε τον κώδικα:
g++ avl.cpp -o run
- Εκτελέστε τον κωδικό.
./run
Πλεονεκτήματα των AVL Trees
- Το ύψος του δέντρου AVL είναι πάντα ισορροπημένο. Το ύψος δεν μεγαλώνει ποτέ πέρα από το log N, όπου N είναι ο συνολικός αριθμός των κόμβων στο δέντρο.
- Παρέχει καλύτερη πολυπλοκότητα χρόνου αναζήτησης σε σύγκριση με τα απλά δέντρα δυαδικής αναζήτησης.
- Τα δέντρα AVL έχουν δυνατότητες αυτοεξισορρόπησης.
Σύνοψη
- Τα δέντρα AVL είναι αυτοεξισορροπούμενα δυαδικά δέντρα αναζήτησης.
- Ο παράγοντας ισορροπίας είναι το θεμελιώδες χαρακτηριστικό των δέντρων AVL
- Ο συντελεστής ισορροπίας ενός κόμβου ορίζεται ως η διαφορά μεταξύ του ύψους του αριστερού και του δεξιού υποδέντρου αυτού του κόμβου.
- Οι έγκυρες τιμές του συντελεστή ισορροπίας είναι -1, 0 και +1.
- Η λειτουργία εισαγωγής και διαγραφής απαιτεί την εκτέλεση περιστροφών μετά την παραβίαση του συντελεστή ισορροπίας.
- Η χρονική πολυπλοκότητα της λειτουργίας εισαγωγής, διαγραφής και αναζήτησης είναι O(log N).
- Τα δέντρα AVL ακολουθούν όλες τις ιδιότητες των Δυαδικών Δέντρων αναζήτησης.
- Το αριστερό υποδέντρο έχει κόμβους που είναι μικρότεροι από τον κόμβο ρίζας. Το δεξί υποδέντρο έχει κόμβους που είναι πάντα μεγαλύτεροι από τον ριζικό κόμβο.
- Τα δέντρα AVL χρησιμοποιούνται όπου η λειτουργία αναζήτησης είναι πιο συχνή σε σύγκριση με τις λειτουργίες εισαγωγής και διαγραφής.