AVL stromy: Rotace, vkládání, mazání s C++ Příklad

Od: Sarah Chen Sarah Chen
Hours aktualizováno

⚡ Chytré shrnutí

AVL stromy jsou samovyvažovací binární vyhledávací stromy, kde výškový rozdíl mezi levým a pravým podstromem každého uzlu zůstává v rozmezí -1, 0 nebo +1, což zaručuje vyhledávací výkon O(log n).

  • 🌲 Definice: Binární vyhledávací strom, ve kterém vyvažovací faktor každého uzlu leží v intervalu {-1, 0, +1}, pojmenovaný po vynálezcích Adelson-Velském a Landisovi.
  • 🇧🇷 Faktor rovnováhy: Vypočítáno jako height(left) − height(right); hodnoty mimo {-1, 0, +1} spustí rotaci pro obnovení rovnováhy.
  • 🔄 Rotace: Čtyři případy – LL, RR, LR a RL – znovu zarovnávají uzly po nevyvážených vloženích nebo odstraněních, aby strom zůstal logaritmický co do výšky.
  • ➕ Vložení: Standardní vkládání BST následované vzestupnou procházkou, která přepočítává vyvažovací faktory a provádí maximálně jednu jednoduchou nebo dvojitou rotaci.
  • ➖ Smazání: Stejné jako mazání BST, ale může kaskádovitě vést k více rotacím ve stromu, protože výška podstromu se může zmenšit u každého předka.
  • ???? Aplikace: Databáze, indexy v paměti, metadata souborového systému a vyhledávací struktury AI používají AVL stromy pro rychlé uspořádané vyhledávání.
Přečíst více

AVL stromy

Co jsou stromy AVL?

AVL stromy jsou binární vyhledávací stromy, ve kterých je výškový rozdíl mezi levým a pravým podstromem každého uzlu -1, 0 nebo +1. Jsou to samovyvažovací BST, které udržují logaritmický čas vyhledávání, pojmenované po vynálezcích Adelson-Velskym a Landisovi (AVL).

Jak AVL Tree funguje?

Abychom pochopili, proč existují AVL stromy, podívejme se, co se pokazí s prázdným Binární vyhledávací stromUvažujme tyto klíče vložené v daném pořadí:

AVL Tree work

Vizualizace stromu AVL

Strom roste lineárně, když klíče přicházejí ve vzestupném pořadí, což degeneruje vyhledávání na O(n). To maří účel BST – pouze vyvážený strom udržuje vyhledávání logaritmické. Nyní se podívejme na stejné klíče vložené v jiném pořadí.

AVL Tree work

Stejné klíče, různé pořadí vkládání, vytvářejí mělčí tvar, takže každé vyhledávání probíhá za O(log n). AVL stromy vynucují tento tvar sledováním výšky při každém vložení a opravou nerovnováhy bez narušení BST pořadí.

Faktor rovnováhy ve stromech AVL

Faktor rovnováhy (BF) tracks výšku každého uzlu, aby se strom mohl za chodu sám vyvažovat.

Vlastnosti bilančního faktoru

Faktor rovnováhy ve stromech AVL

Bilanční faktor AVL strom

  • Faktor vyvážení je rozdíl mezi výškou levého podstromu a výškou pravého podstromu.
  • Balance factor(node) = height(node->left) − height(node->right)
  • Jediné povolené hodnoty jsou −1, 0 a +1.
  • Hodnota -1 znamená, že pravý podstrom obsahuje jednu úroveň navíc – uzel má převahu vpravo.
  • Hodnota +1 znamená, že levý podstrom obsahuje jednu úroveň navíc – uzel má převahu vlevo.
  • Hodnota 0 znamená, že obě strany mají stejnou výšku – uzel je dokonale vyvážený.

AVL rotace

Rotace se spustí vždy, když vložení nebo odstranění poruší pravidlo faktoru vyváženosti. Čtyři případy jsou LL, RR, LR a RL.

Levá – Levá rotace

Tato rotace se provádí, když je nový uzel vložen do levého potomka levého podstromu.

AVL Tree Left – Rotace vlevo

AVL Tree Left – Rotace vlevo

Provede se jediná rotace doprava. Tento případ se spustí, když má uzel BF +2 a jeho levý potomek má BF +1.

Pravá – pravá rotace

Tato rotace se provádí, když je nový uzel vložen do pravého potomka pravého podstromu.

AVL Tree Right – Right Rotation

Provede se jediná rotace doleva. Tento případ se spustí, když uzel má BF −2 a jeho pravý potomek má BF −1.

Rotace vpravo – vlevo

Tato rotace se provádí, když je nový uzel vložen do levého potomka pravého podstromu.

AVL strom Rotace vpravo – vlevo

Spustí se, když BF(uzel) = −2 a BF(pravý potomek) = +1. Otočte pravý potomek a poté uzel doleva.

Otočení vlevo – vpravo

Tato rotace se provádí, když je nový uzel vložen do pravého potomka levého podstromu.

AVL Tree Left – Right Rotation

Spustí se, když BF(uzel) = +2 a BF(levý potomek) = −1. Otočte levého potomka doleva, poté uzel doprava.

Vložení do stromů AVL

Vkládání je téměř identické s obyčejným vkládáním BST. Po každém vložení se strom projde nahoru a znovu vyváží. Vkládání probíhá v nejhorším případě za dobu O(log n).

Vložení do stromů AVL

Implementace vkládání stromu AVL

Krok 1: Vložte uzel pomocí standardního algoritmu BST. Ve výše uvedeném příkladu vložte číslo 160.

Krok 2: Aktualizujte faktor vyvážení každého předka podél cesty vkládání.

Krok 3: Pokud některý z předků poruší rozsah faktoru vyváženosti, proveďte odpovídající rotaci. V příkladu je faktor vyváženosti uzlu 350 porušen, takže rotace LL obnoví rovnováhu.

  1. If BF(node) = +2 a BF(left-child) = +1, proveďte rotaci LL.
  2. If BF(node) = −2 a BF(right-child) = −1, proveďte rotaci RR.
  3. If BF(node) = −2 a BF(right-child) = +1, proveďte rotaci RL.
  4. If BF(node) = +2 a BF(left-child) = −1, proveďte LR rotaci.

SOUVISEJÍCÍ ČLÁNKY

Odstranění ve stromech AVL

Smazání se řídí stejnou logikou jako obyčejný BST a následně se znovu vyvažuje.

Krok 1: Najděte prvek ve stromu.

Krok 2: Odstraňte uzel pomocí standardního mazání BST.

Krok 3: Jsou možné dva případy.

Případ 1: Mazání z pravého podstromu.

  • 1A. If BF(node) = +2 a BF(left-child) = +1, proveďte rotaci LL.
  • 1B. If BF(node) = +2 a BF(left-child) = −1, proveďte LR rotaci.
  • 1C. If BF(node) = +2 a BF(left-child) = 0, proveďte rotaci LL.

Odstranění ve stromech AVL

Případ 2: Mazání z levého podstromu.

  • 2A. If BF(node) = −2 a BF(right-child) = −1, proveďte rotaci RR.
  • 2B. If BF(node) = −2 a BF(right-child) = +1, proveďte rotaci RL.
  • 2C. If BF(node) = −2 a BF(right-child) = 0, proveďte rotaci RR.

Odstranění ve stromech AVL

C++ Příklad AVL stromů

Níže je C++ program implementující AVL stromy:

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

Příklad spuštění výše uvedeného kódu:

  1. Zkopírujte výše uvedený kód a uložte jej do souboru s názvem avl.cpp.
  2. Zkompilujte kód:
g++ avl.cpp -o run
  1. Spusťte kód.
./run

C++ Příklad AVL stromů

Výhody AVL Trees

  • Výška AVL stromu je vždy vyvážená a nikdy nepřekročí log N.
  • Vyhledávání je rychlejší než obyčejný binární vyhledávací strom, protože strom nemůže degenerovat.
  • Samovyvažování je automatické – není nutná žádná přestavba.
  • Deterministický výkon je vhodný pro systémy reálného času a indexy v paměti.

Nejčastější dotazy

AVL strom je samovyvažovací binární vyhledávací strom, kde faktor vyváženosti každého uzlu zůstává v rozsahu {-1, 0, +1}. Rotace obnovují tento invariant při každém vložení nebo smazání.ping vyhledávání, vkládání a mazání v čase O(log n).

Faktor vyváženosti uzlu se rovná výšce (levý podstrom) mínus výška (pravý podstrom). Hodnoty musí ležet v intervalu {-1, 0, +1}. Faktor vyváženosti +2 nebo -2 signalizuje, že vložení nebo odstranění daný uzel narušilo jeho vyváženost a je nutná rotace.

Čtyři rotace jsou LL, RR, LR a RL. LL používá jednu rotaci doprava, RR používá jednu rotaci doleva a LR a RL jsou dvojité rotace, které kombinují jednu rotaci na potomkovi s opačnou rotací na uzlu.

Vkládání se řídí standardním pravidlem BST, poté se strom vrací zpět nahoru a aktualizuje výšky. Pokud některý z předků poruší pravidlo vyváženosti, jedna jednoduchá nebo dvojitá rotace obnoví rovnováhu. Na jedno vkládání je vždy potřeba maximálně jedna rotace.

AVL stromy jsou striktně vyvážené s faktorem vyváženosti maximálně jedna, což umožňuje rychlejší vyhledávání. Červeno-černé stromy umožňují volnější vyvážení, což zlevňuje vkládání a mazání, ale vyhledávání je o něco pomalejší. Databáze preferují červeno-černé stromy pro zátěž s velkým zápisem.

AVL stromy pohánějí indexy databází v paměti, metadata souborového systému, fronty priorit, vyhledávání v telefonním seznamu, kontrolu pravopisu a jakoukoli pracovní zátěž, která vyžaduje deterministické vyhledávání O(log n) a procházení v pořadí pro dotazy rozsahu.

Ano. Systémy umělé inteligence používají AVL stromy pro tabulky symbolů, uspořádaná úložiště rysů, vyvažování kd stromů a vyhledávání nejbližších sousedů ve strukturovaných datech. Jsou také základem řazených indexů vyhledávání v inteligentních vyhledávacích kanálech.

Ano. GitHub Copilot a podobní AI asistenti vytvářejí rutiny pro vkládání, mazání a rotaci v C++, Javanebo Pythona generovat jednotkové testy, které ověřují invariantnost faktoru vyvážení u každé operace.

Shrňte tento příspěvek takto: