Δέντρα AVL: Περιστροφές, Εισαγωγή, Διαγραφή με C++ Παράδειγμα

Τι είναι τα AVL Trees;

Δέντρα AVL είναι δυαδικά δέντρα αναζήτησης στα οποία η διαφορά ύψους μεταξύ του αριστερού και του δεξιού υποδένδρου κάθε κόμβου είναι -1, 0 ή +1. Είναι αυτο-εξισορροπούμενα BST που διατηρούν λογαριθμικό χρόνο αναζήτησης, τα οποία ονομάστηκαν από τους εφευρέτες Adelson-Velsky και Landis (AVL).

Πώς λειτουργεί το AVL Tree;

Για να καταλάβετε γιατί υπάρχουν τα AVL δέντρα, δείτε τι πάει στραβά με ένα απλό δέντρο. Δυαδικό δέντρο αναζήτησηςΘεωρήστε αυτά τα πλήκτρα τοποθετημένα με τη δεδομένη σειρά:

Οπτικοποίηση δέντρου AVL

Το δέντρο αναπτύσσεται γραμμικά όταν τα κλειδιά φτάνουν σε αύξουσα σειρά, εκφυλίζοντας την αναζήτηση σε O(n). Αυτό ακυρώνει τον σκοπό ενός BST — μόνο ένα ισορροπημένο δέντρο διατηρεί την αναζήτηση λογαριθμική. Τώρα εξετάστε τα ίδια κλειδιά που εισάγονται σε διαφορετική σειρά.

Τα ίδια κλειδιά, η διαφορετική σειρά εισαγωγής παράγει ένα πιο ρηχό σχήμα, επομένως κάθε αναζήτηση εκτελείται σε O(log n). Τα δέντρα AVL επιβάλλουν αυτό το σχήμα παρακολουθώντας το ύψος σε κάθε εισαγωγή και διορθώνοντας την ανισορροπία χωρίς να διαταράσσουν τη σειρά BST.

Συντελεστής ισορροπίας στα δέντρα AVL

Ο συντελεστής ισορροπίας (BF) tracks το ύψος κάθε κόμβου, ώστε το δέντρο να μπορεί να αυτο-ισορροπήσει εν κινήσει.

Ιδιότητες του Συντελεστή Ισοζυγίου

Δέντρο AVL παράγοντα ισορροπίας

• Ο συντελεστής ισορροπίας είναι η διαφορά μεταξύ του ύψους του αριστερού υποδέντρου και του ύψους του δεξιού υποδέντρου.
• Balance factor(node) = height(node->left) − height(node->right)
• Οι μόνες επιτρεπόμενες τιμές είναι −1, 0 και +1.
• Μια τιμή −1 σημαίνει ότι το δεξί υποδέντρο περιέχει ένα επιπλέον επίπεδο — ο κόμβος είναι δεξιόστροφος.
• Μια τιμή +1 σημαίνει ότι το αριστερό υποδέντρο περιέχει ένα επιπλέον επίπεδο — ο κόμβος έχει βαρύτητα στα αριστερά.
• Μια τιμή 0 σημαίνει ότι και οι δύο πλευρές έχουν ίσο ύψος — ο κόμβος είναι τέλεια ισορροπημένος.

Περιστροφές AVL

Οι περιστροφές εκτελούνται κάθε φορά που μια εισαγωγή ή διαγραφή παραβιάζει τον κανόνα του παράγοντα ισορροπίας. Οι τέσσερις περιπτώσεις είναι LL, RR, LR και RL.

Αριστερά – Αριστερή Περιστροφή

Αυτή η περιστροφή πραγματοποιείται όταν εισάγεται ένας νέος κόμβος στο αριστερό παιδί του αριστερού υποδέντρου.

AVL Tree Left – Left Rotation

Εκτελείται μία μόνο δεξιά περιστροφή. Αυτή η περίπτωση ενεργοποιείται όταν ένας κόμβος έχει BF +2 και το αριστερό παιδί του έχει BF +1.

Δεξιά – Δεξιά περιστροφή

Αυτή η περιστροφή πραγματοποιείται όταν εισάγεται ένας νέος κόμβος στο δεξί παιδί του δεξιού υποδέντρου.

Εκτελείται μία μόνο αριστερή περιστροφή. Αυτή η περίπτωση ενεργοποιείται όταν ένας κόμβος έχει BF −2 και το δεξί παιδί του έχει BF −1.

Δεξιά – Αριστερά Περιστροφή

Αυτή η περιστροφή πραγματοποιείται όταν εισάγεται ένας νέος κόμβος στο αριστερό παιδί του δεξιού υποδέντρου.

Ενεργοποιείται όταν BF(κόμβος) = −2 και BF(δεξιό θυγατρικό) = +1. Περιστρέψτε δεξιά το δεξί θυγατρικό στοιχείο και, στη συνέχεια, περιστρέψτε αριστερά τον κόμβο.

Περιστροφή Αριστερά – Δεξιά

Αυτή η περιστροφή πραγματοποιείται όταν εισάγεται ένας νέος κόμβος στο δεξί παιδί του αριστερού υποδέντρου.

Ενεργοποιείται όταν BF(κόμβος) = +2 και BF(αριστερό-θυγατρικό) = −1. Περιστρέψτε το αριστερό θυγατρικό στοιχείο αριστερά και, στη συνέχεια, περιστρέψτε τον κόμβο δεξιά.

Εισαγωγή σε δέντρα AVL

Η εισαγωγή είναι σχεδόν πανομοιότυπη με μια απλή εισαγωγή BST. Μετά από κάθε εισαγωγή, το δέντρο ανεβαίνει και επανισορροπεί. Η εισαγωγή εκτελείται σε χρόνο χειρότερης περίπτωσης O(log n).

Εφαρμογή εισαγωγής δέντρου AVL

Βήμα 1: Εισαγάγετε τον κόμβο χρησιμοποιώντας τον τυπικό αλγόριθμο BST. Στο παραπάνω παράδειγμα, εισαγάγετε 160.

Βήμα 2: Ενημερώστε τον συντελεστή ισορροπίας κάθε προγόνου κατά μήκος της διαδρομής εισαγωγής.

Βήμα 3: Εάν κάποιος πρόγονος παραβιάζει το εύρος του συντελεστή ισορροπίας, εκτελέστε την αντίστοιχη περιστροφή. Στο παράδειγμα, ο συντελεστής ισορροπίας του κόμβου 350 παραβιάζεται, επομένως μια περιστροφή LL αποκαθιστά την ισορροπία.

1. If BF(node) = +2 και BF(left-child) = +1, εκτελέστε περιστροφή LL.
2. If BF(node) = −2 και BF(right-child) = −1, εκτελέστε περιστροφή RR.
3. If BF(node) = −2 και BF(right-child) = +1, εκτελέστε περιστροφή δεξιά.
4. If BF(node) = +2 και BF(left-child) = −1, εκτελέστε περιστροφή αριστερά.

Διαγραφή σε AVL Trees

Η διαγραφή ακολουθεί την ίδια λογική με ένα απλό BST και επαναισορροπείται στη συνέχεια.

Βήμα 1: Βρείτε το στοιχείο στο δέντρο.

Βήμα 2: Διαγράψτε τον κόμβο χρησιμοποιώντας την τυπική διαγραφή BST.

Βήμα 3: Δύο περιπτώσεις είναι πιθανές.

Υπόθεση 1: Διαγραφή από το δεξί υποδέντρο.

• 1A. If BF(node) = +2 και BF(left-child) = +1, εκτελέστε περιστροφή LL.
• 1B. If BF(node) = +2 και BF(left-child) = −1, εκτελέστε περιστροφή αριστερά.
• 1C If BF(node) = +2 και BF(left-child) = 0, εκτελέστε περιστροφή LL.

Υπόθεση 2: Διαγραφή από το αριστερό υποδέντρο.

• 2A. If BF(node) = −2 και BF(right-child) = −1, εκτελέστε περιστροφή RR.
• 2B. If BF(node) = −2 και BF(right-child) = +1, εκτελέστε περιστροφή δεξιά.
• 2C If BF(node) = −2 και BF(right-child) = 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 {
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;
        return 0;
    }

    struct node *llrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->left;
        p->left = tp->right;
        tp->right = p;
        return tp;
    }

    struct node *rrrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->right;
        p->right = tp->left;
        tp->left = p;
        return tp;
    }

    struct node *rlrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->right;
        struct node *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 = n;
        struct node *tp = p->left;
        struct node *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) {
            r = new struct node;
            r->data = data;
            r->left = r->right = NULL;
            r->height = 1;
            return r;
        }
        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 << "\nEmpty 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 *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 = rrrotation(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(); 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);
}

Εκτελώντας ένα παράδειγμα του παραπάνω κώδικα:

1. Αντιγράψτε τον παραπάνω κώδικα και αποθηκεύστε τον σε ένα αρχείο με όνομα avl.cpp.
2. Μεταγλωττίστε τον κώδικα:

g++ avl.cpp -o run

3. Εκτελέστε τον κωδικό.

./run

Πλεονεκτήματα των AVL Trees

• Το ύψος του AVL Tree είναι πάντα ισορροπημένο και δεν υπερβαίνει ποτέ το log N.
• Η αναζήτηση είναι ταχύτερη από ένα απλό Δυαδικό Δέντρο Αναζήτησης επειδή το δέντρο δεν μπορεί να εκφυλιστεί.
• Η αυτο-εξισορρόπηση είναι αυτόματη — δεν απαιτείται βήμα ανακατασκευής.
• Η ντετερμινιστική απόδοση ταιριάζει σε συστήματα πραγματικού χρόνου και σε ευρετήρια μνήμης.

Συχνές Ερωτήσεις