AVL-puud: pööramised, sisestamine, kustutamine koos C++ Näide

⚡ Nutikas kokkuvõte

AVL-puud on isetasakaalustuvad binaarsed otsingupuud, kus iga sõlme vasaku ja parema alampuu kõrguste vahe jääb -1, 0 või +1 piiresse, tagades O(log n) otsingu jõudluse.

🌲 Määratlus: Binaarne otsingupuu, milles iga sõlme tasakaalutegur asub vahemikus {-1, 0, +1} ning mis on nimetatud leiutajate Adelson-Velsky ja Landise järgi.
🇧🇷 Tasakaalu tegur: Arvutatakse kujul height(left) − height(right); väärtused väljaspool {-1, 0, +1} käivitavad tasakaalu taastamiseks pöörlemise.
🔄 Pöörded: Neli juhtumit – LL, RR, LR ja RL – joondavad sõlmed pärast tasakaalustamata lisamisi või kustutamisi ümber, et hoida puu kõrgus logaritmilisena.
➕ Lisamine: Standardne BST sisestus, millele järgneb ülespoole suunatud kõndimine, mis arvutab uuesti tasakaalutegureid ja sooritab maksimaalselt ühe või kahekordse pöörde.
➖ Kustutamine: Sama mis BST kustutamine, aga võib puus mitu korda ülespoole rotatsiooni põhjustada, kuna alampuu kõrgus võib iga eellase juures kahaneda.
🚀 Rakendused: Andmebaasid, mälusisesed indeksid, failisüsteemi metaandmed ja tehisintellekti otsingustruktuurid kasutavad kiirete järjestatud otsingute jaoks AVL-puid.

Loe rohkem

Mis on AVL-puud?

AVL puud on binaarsed otsingupuud, mille iga sõlme vasaku ja parema alampuu kõrguste vahe on -1, 0 või +1. Need on isetasakaalustuvad BST-d, mis säilitavad logaritmilise otsinguaja ning on nimetatud leiutajate Adelson-Velsky ja Landise (AVL) järgi.

Kuidas AVL Tree töötab?

AVL-puude olemasolu mõistmiseks vaadake, mis tavalise puuga valesti läheb. BinaarotsingupuuVaatleme neid võtmeid antud järjekorras sisestatuna:

AVL-i puu visualiseerimine

Puu kasvab lineaarselt, kui võtmed saabuvad kasvavas järjekorras, degenereerides otsingu väärtuseks O(n). See kaotab BST eesmärgi – ainult tasakaalustatud puu hoiab otsingu logaritmilisena. Nüüd vaadake samu võtmeid, mis on sisestatud teises järjekorras.

Samad võtmed, erinev sisestamise järjekord annab madalama kuju, seega iga otsing toimub O(log n) ühikutes. AVL-puud jõustavad seda kuju, jälgides iga sisestamise ajal kõrgust ja korrigeerides tasakaalustamatust ilma BST-järjestust rikkumata.

Tasakaalutegur AVL-puudes

Tasakaalutegur (BF) tracks iga sõlme kõrgus, et puu saaks lennult ennast tasakaalustuda.

Tasakaaluteguri omadused

Tasakaaluteguri AVL puu

Tasakaalutegur on vasakpoolse ja parempoolse alampuu kõrguste vahe.
Balance factor(node) = height(node->left) − height(node->right)
Ainsad lubatud väärtused on −1, 0 ja +1.
Väärtus −1 tähendab, et parempoolne alampuu sisaldab ühte lisataset – sõlm on parempoolsete arvudega raskem.
Väärtus +1 tähendab, et vasakpoolne alampuu sisaldab ühte lisataset – sõlm on vasakraske.
Väärtus 0 tähendab, et mõlemal poolel on võrdne kõrgus – sõlm on ideaalselt tasakaalus.

AVL-i pöörded

Rotatsioonid käivituvad alati, kui lisamine või kustutamine rikub tasakaaluteguri reeglit. Need neli juhtu on LL, RR, LR ja RL.

Vasak – vasakule pööramine

See pööramine toimub siis, kui uus sõlm lisatakse vasaku alampuu vasakpoolsesse alampuusse.

AVL-puu vasakule – vasakule pööramisele

Teostatakse üks parempööre. See juhtum käivitub siis, kui sõlmel on BF +2 ja selle vasakul lapsel on BF +1.

Paremale – paremale pööramine

See pööramine toimub siis, kui uus sõlm sisestatakse parema alampuu paremasse alampuusse.

Teostatakse üks vasakpööre. See juhtum käivitub siis, kui sõlmel on BF −2 ja selle paremal lapsel on BF −1.

Paremale – vasakule pööramine

See pööramine toimub siis, kui parempoolse alampuu vasakpoolsesse alampuusse lisatakse uus sõlm.

Käivitub, kui BF(node) = −2 ja BF(right-child) = +1. Pööra paremat tütart paremale, seejärel pööra sõlme vasakule.

Vasak – parem pööramine

See pööramine toimub siis, kui uus sõlm lisatakse vasaku alampuu paremasse alampuusse.

Käivitub, kui BF(node) = +2 ja BF(vasakpoolne-laps) = −1. Pööra vasakpoolset last vasakule, seejärel pööra sõlme paremale.

Sisestamine AVL Puudesse

Lisamine on peaaegu identne tavalise BST lisamisega. Pärast iga lisamist liigub puu edasi ja tasakaalustub uuesti. Lisamine toimub halvimal juhul O(log n) ajaga.

AVL-i puu sisestamise rakendamine

Samm 1: Sisesta sõlm standardse BST algoritmi abil. Ülaltoodud näites sisesta 160.

Samm 2: Uuenda iga eellase tasakaalutegurit sisestamise teel.

Samm 3: Kui mõni eellane rikub tasakaaluteguri vahemikku, teostage sobituspööramine. Näites on sõlme 350 tasakaalutegur rikutud, seega taastab tasakaalu LL-pööramine.

If BF(node) = +2 ja BF(left-child) = +1, teosta LL-pöörlemine.
If BF(node) = −2 ja BF(right-child) = −1, teostage RR-pöörlemine.
If BF(node) = −2 ja BF(right-child) = +1, teostage RL-pööramine.
If BF(node) = +2 ja BF(left-child) = −1, teosta LR-pöörlemine.

Kustutamine AVL-puudest

Kustutamine järgib sama loogikat nagu tavaline BST ja tasakaalustab pärast uuesti.

Samm 1: Leidke puust element.

Samm 2: Kustuta sõlm standardse BST kustutamise abil.

Samm 3: Võimalikud on kaks juhtumit.

Case 1: Kustutamine parempoolsest alampuust.

1A. If BF(node) = +2 ja BF(left-child) = +1, teosta LL-pöörlemine.
1B. If BF(node) = +2 ja BF(left-child) = −1, teosta LR-pöörlemine.
1C. If BF(node) = +2 ja BF(left-child) = 0, teosta LL-pöörlemine.

Case 2: Vasakpoolsest alampuust kustutamine.

2A. If BF(node) = −2 ja BF(right-child) = −1, teostage RR-pöörlemine.
2B. If BF(node) = −2 ja BF(right-child) = +1, teostage RL-pööramine.
2C. If BF(node) = −2 ja BF(right-child) = 0, teostage RR-pöörlemine.

C++ AVL-puude näide

Allpool on C++ AVL-puid rakendav programm:

#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);
}

Ülaltoodud koodi käivitamise näide:

Kopeeri ülaltoodud kood ja salvesta see faili nimega avl.cpp.
Koostage kood:

g++ avl.cpp -o run

Käivitage kood.

./run

AVL-puude eelised

AVL-puu kõrgus on alati tasakaalus ega kasva kunagi üle log N.
Otsing on kiirem kui tavaline binaarne otsingupuu, sest puu ei saa degenereeruda.
Ise tasakaalustamine on automaatne – ümberehitust pole vaja.
Deterministlik jõudlus sobib reaalajas süsteemidele ja mälusisestele indeksitele.

KKK

AVL-puu on isetasakaalustuv binaarne otsingupuu, kus iga sõlme tasakaalutegur jääb vahemikku {-1, 0, +1}. Pööramised taastavad selle invariantti iga sisestamise või kustutamise korral, keeping otsi, sisesta ja kustuta asukohas O(log n).

Sõlme tasakaalutegur on võrdne kõrguse (vasak alampuu) ja kõrguse (parem alampuu) vahega. Väärtused peavad jääma vahemikku {-1, 0, +1}. Tasakaalutegur +2 või -2 näitab, et lisamine või kustutamine on sõlme tasakaalustamata jätnud ja on vaja rotatsiooni.

Neli pööret on LL, RR, LR ja RL. LL kasutab ühte paremale pööret, RR kasutab ühte vasakule pööret ning LR ja RL on topeltpöörded, mis ühendavad ühe pöörde lapsel vastaspöörlemisega sõlmel.

Lisamine järgib standardset BST reeglit, seejärel kõnnib puu tagasi üles, uuendades kõrgusi. Kui mõni eellane rikub tasakaalureeglit, taastab tasakaalu üks või kaks pööret. Lisamise kohta on vaja maksimaalselt ühte pööret.

AVL-puud on rangelt tasakaalustatud, tasakaalustusteguriga maksimaalselt üks, mis võimaldab kiiremaid otsinguid. Puna-mustad puud võimaldavad lõdvemat tasakaalu, mis muudab sisestamise ja kustutamise odavamaks, kuid otsingu veidi aeglasemaks. Andmebaasid eelistavad puna-musta puud kirjutamismahukate koormuste korral.

AVL-puud toetavad mälusiseste andmebaaside indekseid, failisüsteemi metaandmeid, prioriteetide järjekordi, telefoniraamatu otsinguid, õigekirjakontrolli ja mis tahes töökoormust, mis vajab deterministlikku O(log n) otsingut ja vahemikupäringute puhul järjestuse sisest läbimist.

Jah. Tehisintellekti süsteemid kasutavad AVL-puid sümbolitabelite, järjestatud tunnuste salvestamise, kd-puu tasakaalustamise ja struktureeritud andmete lähima naabri otsingu jaoks. Need on ka intelligentsete otsingukanalite järjestatud otsinguindeksite aluseks.

Jah. GitHub Copilot ja sarnased tehisintellekti assistendid toetavad sisestamise, kustutamise ja pööramise rutiine. C++, Javavõi Pythonja genereerida ühikteste, mis kontrollivad tasakaaluteguri invariantsust iga operatsiooni puhul.

AVL-puud: pööramised, sisestamine, kustutamine koos C++ Näide

Mis on AVL-puud?

Kuidas AVL Tree töötab?

Tasakaalutegur AVL-puudes

Tasakaaluteguri omadused

AVL-i pöörded

Vasak – vasakule pööramine

Paremale – paremale pööramine

Paremale – vasakule pööramine

Vasak – parem pööramine

Sisestamine AVL Puudesse

Kustutamine AVL-puudest

C++ AVL-puude näide

AVL-puude eelised

KKK

Võta see postitus kokku järgmiselt:

Tellige uudiskiri

Mis on AVL-puud?

Kuidas AVL Tree töötab?

Tasakaalutegur AVL-puudes

Tasakaaluteguri omadused

AVL-i pöörded

Vasak – vasakule pööramine

Paremale – paremale pööramine

Paremale – vasakule pööramine

Vasak – parem pööramine

Sisestamine AVL Puudesse

SEOTUD ARTIKLID

Kustutamine AVL-puudest

C++ AVL-puude näide

AVL-puude eelised

KKK

Võta see postitus kokku järgmiselt:

Tellige uudiskiri