AVL-puut: kierrokset, lisäys, poisto C++ esimerkki

by: Sarah Chen Sarah Chen
Hours Päivitetty

⚡ Älykäs yhteenveto

AVL-puut ovat itsetasapainottuvia binäärihakupuita, joissa jokaisen solmun vasemman ja oikean alipuun välinen korkeusero pysyy välillä -1, 0 tai +1, mikä takaa O(log n) -haun suorituskyvyn.

  • 🌲 Määritelmä: Binäärihakupuu, jossa jokaisen solmun tasapainokerroin on {-1, 0, +1}, nimetty keksijöiden Adelson-Velskyn ja Landisin mukaan.
  • 🇧🇷 Tasapainokerroin: Lasketaan muodossa height(left) − height(right); arvot {-1, 0, +1} ulkopuolella käynnistävät kierron tasapainon palauttamiseksi.
  • 🔄 Kierrokset: Neljä tapausta – LL, RR, LR ja RL – uudelleenjärjestävät solmut epätasapainoisten lisäysten tai poistojen jälkeen, jotta puu pysyisi logaritmisena korkeudeltaan.
  • ➕ Lisäys: Standardi BST-insertti, jota seuraa ylöspäin suuntautuva kävely, joka laskee uudelleen tasapainokertoimet ja suorittaa enintään yhden yksittäisen tai kahden kierroksen.
  • ➖ poisto: Sama kuin BST-deleetio, mutta voi aiheuttaa useita rotaatioita puussa ylöspäin, koska alipuun korkeus voi kutistua jokaisen esi-isän kohdalla.
  • 🚀 Sovellukset: Tietokannat, muistin sisäiset indeksit, tiedostojärjestelmän metatiedot ja tekoälyhakurakenteet käyttävät AVL-puita nopeisiin ja järjestettyihin hakuihin.
Lue lisää

AVL puut

Mitä AVL-puut ovat?

AVL puut ovat binaarisia hakupuita, joissa jokaisen solmun vasemman ja oikean alipuun välinen korkeusero on -1, 0 tai +1. Ne ovat itsetasapainottuvia BST:itä, jotka ylläpitävät logaritmista hakuaikaa ja jotka on nimetty keksijöiden Adelson-Velskyn ja Landisin (AVL) mukaan.

Kuinka AVL Tree toimii?

Ymmärtääksesi, miksi AVL-puita on olemassa, katso, mikä menee pieleen tavallisessa Binaarinen hakupuuTarkastellaan näitä avaimia annetussa järjestyksessä lisättyinä:

AVL Puutyö

AVL-puun visualisointi

Puu kasvaa lineaarisesti, kun avaimet saapuvat nousevassa järjestyksessä, mikä rappeuttaa haun arvoon O(n). Tämä tekee BST:n tarkoituksen tyhjäksi – vain tasapainoinen puu pitää haun logaritmisena. Katsotaanpa nyt samoja avaimia eri järjestyksessä.

AVL Puutyö

Samat avaimet, eri lisäysjärjestys tuottaa matalamman muodon, joten jokainen haku suoritetaan muodossa O(log n). AVL-puut valvovat tätä muotoa tarkkailemalla korkeutta jokaisella lisäyksellä ja korjaamalla epätasapainoa rikkomatta BST-järjestystä.

Tasapainotekijä AVL-puissa

Tasapainokerroin (BF) tracks jokaisen solmun korkeus, jotta puu voi tasapainottua lennossa.

Tasapainotekijän ominaisuudet

Tasapainotekijä AVL-puissa

Tasapainotekijä AVL-puu

  • Tasapainokerroin on vasemman ja oikean alipuun korkeuden välinen ero.
  • Balance factor(node) = height(node->left) − height(node->right)
  • Sallitut arvot ovat vain −1, 0 ja +1.
  • Arvo −1 tarkoittaa, että oikeanpuoleisessa alipuussa on yksi ylimääräinen taso – solmu on oikeapainotteinen.
  • Arvo +1 tarkoittaa, että vasemmassa alipuussa on yksi ylimääräinen taso – solmu on vasemmalta painottuva.
  • Arvo 0 tarkoittaa, että molemmilla puolilla on sama korkeus – solmu on täysin tasapainossa.

AVL Rotations

Rotaatioita suoritetaan aina, kun lisäys tai poisto rikkoo tasapainokertoimen säännön. Neljä tapausta ovat LL, RR, LR ja RL.

Vasen – Vasen kierto

Tämä kierto suoritetaan, kun uusi solmu lisätään vasemman alipuun vasempaan lapseen.

AVL-puu vasemmalle – vasemmalle kierto

AVL-puu vasemmalle – vasemmalle kierto

Yksi oikealle kiertävä solmu suoritetaan. Tämä tapaus aktivoituu, kun solmun BF on +2 ja sen vasemmanpuoleisen lapsen BF on +1.

Oikea – oikea kierto

Tämä kierto suoritetaan, kun uusi solmu lisätään oikean alipuun oikeaan lapseen.

AVL Tree Right – Oikea kierto

Suoritetaan yksi vasemmalle kiertävä liike. Tämä tapaus aktivoituu, kun solmun BF −2 ja sen oikeanpuoleisen lapsen BF −1 on olemassa.

Oikea – Vasen kierto

Tämä kierto suoritetaan, kun uusi solmu lisätään oikean alipuun vasempaan lapseen.

AVL-puu oikealle – vasemmalle kierto

Laukaistaan, kun BF(solmu) = −2 ja BF(oikea lapsi) = +1. Kierrä oikeaa lasta oikealle ja sitten solmua vasemmalle.

Vasen – Oikea kierto

Tämä kierto suoritetaan, kun uusi solmu lisätään vasemman alipuun oikeaan lapseen.

AVL-puu vasen – oikea kierto

Laukaisee, kun BF(solmu) = +2 ja BF(vasen lapsi) = −1. Kierrä vasenta lasta vasemmalle ja sitten solmua oikealle.

Lisäys AVL-puihin

Lisäys on lähes identtinen tavallisen BST-lisäyksen kanssa. Jokaisen lisäyksen jälkeen puu kävelee ylös ja tasapainottuu uudelleen. Lisäys suoritetaan pahimmassa tapauksessa ajassa O(log n).

Lisäys AVL-puihin

AVL-puun lisäyksen toteutus

Vaihe 1: Lisää solmu käyttämällä BST-algoritmin standardia. Yllä olevassa esimerkissä lisää luku 160.

Vaihe 2: Päivitä jokaisen lisäyspolun varrella olevan esi-isän tasapainokerroin.

Vaihe 3: Jos jokin kantasolmu rikkoo tasapainokertoimen aluetta, suorita vastaava kierto. Esimerkissä solmun 350 tasapainokerroin rikkoutuu, joten LL-kierto palauttaa tasapainon.

  1. If BF(node) = +2 ja BF(left-child) = +1, suorita LL-kierto.
  2. If BF(node) = −2 ja BF(right-child) = −1, suorita RR-kierto.
  3. If BF(node) = −2 ja BF(right-child) = +1, suorita RL-kierto.
  4. If BF(node) = +2 ja BF(left-child) = −1, suorita LR-kierto.

AIHEESEEN LIITTYVÄT ARTIKKELIT

Poisto AVL-puista

Poisto noudattaa samaa logiikkaa kuin tavallinen BST ja tasapainottuu uudelleen jälkeenpäin.

Vaihe 1: Etsi elementti puusta.

Vaihe 2: Poista solmu käyttämällä BST:n vakiopoistoa.

Vaihe 3: Kaksi mahdollista tapausta.

Case 1: Poistetaan oikeasta alipuusta.

  • 1A. If BF(node) = +2 ja BF(left-child) = +1, suorita LL-kierto.
  • 1B. If BF(node) = +2 ja BF(left-child) = −1, suorita LR-kierto.
  • 1C. If BF(node) = +2 ja BF(left-child) = 0, suorita LL-kierto.

Poisto AVL-puista

Case 2: Poistetaan vasemmasta alipuusta.

  • 2A. If BF(node) = −2 ja BF(right-child) = −1, suorita RR-kierto.
  • 2B. If BF(node) = −2 ja BF(right-child) = +1, suorita RL-kierto.
  • 2C. If BF(node) = −2 ja BF(right-child) = 0, suorita RR-kierto.

Poisto AVL-puista

C++ Esimerkki AVL-puista

Alla on a C++ AVL-puita toteuttava ohjelma:

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

Yllä olevan koodin suoritusesimerkki:

  1. Kopioi yllä oleva koodi ja tallenna se tiedostoon nimeltä avl.cpp.
  2. Kokoa koodi:
g++ avl.cpp -o run
  1. Suorita koodi.
./run

C++ Esimerkki AVL-puista

AVL-puiden edut

  • AVL-puun korkeus on aina tasapainossa eikä se koskaan kasva yli log N:n.
  • Haku on nopeampaa kuin tavallinen binäärinen hakupuu, koska puu ei voi rappeutua.
  • Itsetasapainotus on automaattinen – uudelleenrakennusvaihetta ei tarvita.
  • Deterministinen suorituskyky sopii reaaliaikaisiin järjestelmiin ja muistissa oleviin indekseihin.

UKK

AVL-puu on itseään tasapainottava binäärihakupuu, jossa jokaisen solmun tasapainokerroin pysyy välillä {-1, 0, +1}. Kierrot palauttavat tämän invariantin jokaisella lisäyksellä tai poistolla, pidäping etsi, lisää ja poista kohdassa O(log n).

Solmun tasapainokerroin on yhtä kuin korkeus (vasen alipuu) miinus korkeus (oikea alipuu). Arvojen on oltava välillä {-1, 0, +1}. Tasapainokerroin +2 tai -2 merkitsee, että lisäys tai poisto on tasapainottanut solmua ja vaaditaan kierto.

Neljä kiertoa ovat LL, RR, LR ja RL. LL käyttää yhtä oikealle suuntautuvaa kiertoa, RR käyttää yhtä vasemmalle suuntautuvaa kiertoa ja LR ja RL ovat kaksoiskiertoja, jotka yhdistävät yhden rotaation lapsisolmulla ja vastakkaisen rotaation solmulla.

Lisäys noudattaa BST-standardisääntöä, minkä jälkeen puu palaa ylös päivittäen korkeuksia. Jos jokin esi-isä rikkoo tasapainosäännön, yksi tai kaksi kiertoa palauttaa tasapainon. Lisäystä kohden tarvitaan enintään yksi kierto.

AVL-puut ovat tiukasti tasapainotettuja, ja niiden tasapainotuskerroin on enintään yksi, mikä nopeuttaa hakuja. Puna-mustat puut mahdollistavat löyhemmän tasapainotuksen, mikä tekee lisäyksestä ja poistamisesta halvempaa, mutta haku on hieman hitaampaa. Tietokannat suosivat puna-mustia puuta kirjoituspainotteisissa kuormissa.

AVL-puut mahdollistavat muistissa olevien tietokantaindekseiden, tiedostojärjestelmän metatietojen, prioriteettijonojen, puhelinluettelohakujen, oikolukujen tarkistukset ja kaikki työkuormit, jotka vaativat determinististä O(log n) -hakua sekä järjestyksessä tapahtuvaa läpikulkua aluekyselyissä.

Kyllä. Tekoälyjärjestelmät käyttävät AVL-puita symbolitaulukoihin, järjestettyihin ominaisuustallennuksiin, kd-puun tasapainottamiseen ja lähimmän naapurin hakuun strukturoidussa datassa. Ne tukevat myös älykkäiden hakuputkien järjestettyjä hakuindeksejä.

Kyllä. GitHub Copilot ja vastaavat tekoälyavustajat tukevat lisäys-, poisto- ja kiertorutiineja C++, Javatai Pythonja luo yksikkötestejä, jotka varmistavat tasapainotekijän pysyvyyden invarianttina jokaisessa operaatiossa.

Tiivistä tämä viesti seuraavasti: