Drzewa AVL: Obroty, Wstawianie, Usuwanie za pomocą C++ Przykład

Przez: Sara Chen Sara Chen
Hours Zaktualizowano

⚡ Inteligentne podsumowanie

Drzewa AVL to samobalansujące się drzewa wyszukiwań binarnych, w których różnica wysokości między lewym i prawym poddrzewem każdego węzła mieści się w granicach -1, 0 lub +1, gwarantując wydajność wyszukiwania na poziomie O(log n).

  • 🌲 Definicja: Drzewo poszukiwań binarnych, w którym współczynnik równowagi każdego węzła leży w przedziale {-1, 0, +1}, nazwane na cześć wynalazców Adelsona-Velsky'ego i Landisa.
  • ⚖️. Współczynnik równowagi: Obliczane jako wysokość(lewa) − wysokość(prawa); wartości spoza przedziału {-1, 0, +1} powodują obrót w celu przywrócenia równowagi.
  • 🔄 Rotacje: Cztery przypadki — LL, RR, LR i RL — polegają na ponownym wyrównywaniu węzłów po niezrównoważonych wstawieniach lub usunięciach w celu utrzymania logarytmicznej wysokości drzewa.
  • ➕ Wprowadzenie: Standardowa wkładka BST, po której następuje ruch w górę, który ponownie oblicza współczynniki równowagi i wykonuje maksymalnie jeden pojedynczy lub podwójny obrót.
  • ➖ Usunięcie: Podobnie jak usunięcie BST, ale może powodować kaskadowe wykonywanie wielu obrotów w górę drzewa, ponieważ wysokość poddrzewa może się zmniejszać przy każdym przodku.
  • 🚀 Aplikacje: Bazy danych, indeksy w pamięci, metadane systemu plików i struktury wyszukiwania AI wykorzystują drzewa AVL do szybkiego, uporządkowanego wyszukiwania.
Czytaj więcej

Drzewa AVL

Czym są drzewa AVL?

Drzewa AVL Są to binarne drzewa poszukiwań, w których różnica wysokości między lewym a prawym poddrzewem każdego węzła wynosi -1, 0 lub +1. Są to samobalansujące się drzewa BST, które utrzymują logarytmiczny czas wyszukiwania, nazwane na cześć wynalazców Adelson-Velsky i Landis (AVL).

Jak działa drzewo AVL?

Aby zrozumieć, dlaczego istnieją drzewa AVL, przyjrzyjmy się temu, co jest nie tak z prostym drzewem Drzewo wyszukiwania binarnegoRozważ wstawienie tych kluczy w podanej kolejności:

Praca nad drzewem AVL

Wizualizacja drzewa AVL

Drzewo rośnie liniowo, gdy klucze pojawiają się w kolejności rosnącej, degenerując wyszukiwanie do O(n). To zaprzecza celowi BST — tylko zrównoważone drzewo utrzymuje logarytmiczne wyszukiwanie. Teraz spójrz na te same klucze wstawione w innej kolejności.

Praca nad drzewem AVL

Te same klucze, inna kolejność wstawiania, tworzą płytszy kształt, więc każde wyszukiwanie przebiega w czasie O(log n). Drzewa AVL wymuszają ten kształt, monitorując wysokość przy każdym wstawianiu i korygując nierównowagę bez naruszania kolejności BST.

Współczynnik równowagi w drzewach AVL

Współczynnik równowagi (BF) tracwysokość każdego węzła, dzięki czemu drzewo może samoczynnie utrzymywać równowagę w locie.

Właściwości współczynnika równowagi

Współczynnik równowagi w drzewach AVL

Drzewo AVL współczynnika równowagi

  • Współczynnik równowagi to różnica między wysokością lewego poddrzewa i wysokością prawego poddrzewa.
  • Balance factor(node) = height(node->left) − height(node->right)
  • Jedyne dozwolone wartości to −1, 0 i +1.
  • Wartość −1 oznacza, że ​​prawe poddrzewo zawiera jeden dodatkowy poziom — węzeł jest ciężki po prawej stronie.
  • Wartość +1 oznacza, że ​​lewe poddrzewo zawiera jeden dodatkowy poziom — węzeł jest położony bardziej po lewej stronie.
  • Wartość 0 oznacza, że ​​obie strony mają taką samą wysokość — węzeł jest idealnie zrównoważony.

Rotacje AVL

Rotacje są przeprowadzane za każdym razem, gdy wstawienie lub usunięcie narusza regułę współczynnika równowagi. Cztery przypadki to LL, RR, LR i RL.

W lewo – obrót w lewo

Ten obrót jest wykonywany, gdy nowy węzeł jest wstawiany po lewej stronie potomka lewego poddrzewa.

Drzewo AVL w lewo – obrót w lewo

Drzewo AVL w lewo – obrót w lewo

Wykonywany jest pojedynczy obrót w prawo. Ten przypadek występuje, gdy węzeł ma BF +2, a jego lewy potomek ma BF +1.

Prawo – obrót w prawo

Ten obrót jest wykonywany, gdy nowy węzeł jest wstawiany po prawym dziecku prawego poddrzewa.

Drzewo AVL w prawo – obrót w prawo

Wykonywany jest pojedynczy obrót w lewo. Ten przypadek występuje, gdy węzeł ma BF −2, a jego prawy potomek ma BF −1.

Prawo – obrót w lewo

Ten obrót jest wykonywany, gdy nowy węzeł jest wstawiany w lewym dziecku prawego poddrzewa.

Drzewo AVL w prawo – obrót w lewo

Wywołuje się, gdy BF(węzeł) = −2 i BF(prawe dziecko) = +1. Obróć prawe dziecko w prawo, a następnie obróć węzeł w lewo.

Obrót w lewo – w prawo

Ten obrót jest wykonywany, gdy nowy węzeł jest wstawiany w prawym dziecku lewego poddrzewa.

Obrót drzewa AVL w lewo – w prawo

Wywołuje się, gdy BF(węzeł) = +2 i BF(lewe dziecko) = −1. Obróć lewe dziecko w lewo, a następnie obróć węzeł w prawo.

Wstawienie do drzew AVL

Wstawianie jest niemal identyczne jak wstawianie zwykłego BST. Po każdym wstawieniu drzewo przechodzi w górę i ponownie się równoważy. Wstawienie wykonuje się w najgorszym przypadku w czasie O(log n).

Wstawienie do drzew AVL

Implementacja wstawiania drzewa AVL

Krok 1: Wstaw węzeł, używając standardowego algorytmu BST. W powyższym przykładzie wstaw 160.

Krok 2: Zaktualizuj współczynnik równowagi każdego przodka na ścieżce wprowadzania.

Krok 3: Jeśli którykolwiek z przodków narusza zakres współczynnika równowagi, wykonaj rotację dopasowującą. W tym przykładzie współczynnik równowagi węzła 350 jest naruszony, więc rotacja LL przywraca równowagę.

  1. If BF(node) = +2 oraz BF(left-child) = +1, wykonaj obrót LL.
  2. If BF(node) = −2 oraz BF(right-child) = −1, wykonaj rotację RR.
  3. If BF(node) = −2 oraz BF(right-child) = +1, wykonaj obrót RL.
  4. If BF(node) = +2 oraz BF(left-child) = −1, wykonaj obrót LR.

POWIĄZANE ARTYKUŁY

Usuwanie w drzewach AVL

Usunięcie odbywa się według tej samej logiki co w przypadku zwykłego BST, a następnie następuje ponowne zrównoważenie.

Krok 1: Znajdź element w drzewie.

Krok 2: Usuń węzeł, korzystając ze standardowej procedury usuwania BST.

Krok 3: Możliwe są dwa przypadki.

Sprawa 1: Usuwanie z prawego poddrzewa.

  • 1A. If BF(node) = +2 oraz BF(left-child) = +1, wykonaj obrót LL.
  • 1B. If BF(node) = +2 oraz BF(left-child) = −1, wykonaj obrót LR.
  • 1C. If BF(node) = +2 oraz BF(left-child) = 0, wykonaj obrót LL.

Usuwanie w drzewach AVL

Sprawa 2: Usuwanie z lewego poddrzewa.

  • 2A. If BF(node) = −2 oraz BF(right-child) = −1, wykonaj rotację RR.
  • 2B. If BF(node) = −2 oraz BF(right-child) = +1, wykonaj obrót RL.
  • 2C. If BF(node) = −2 oraz BF(right-child) = 0, wykonaj rotację RR.

Usuwanie w drzewach AVL

C++ Przykład drzew AVL

Poniżej znajduje C++ program implementujący drzewa 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);
}

Przykład działania powyższego kodu:

  1. Skopiuj powyższy kod i zapisz go w pliku o nazwie avl.cpp.
  2. Skompiluj kod:
g++ avl.cpp -o run
  1. Uruchom kod.
./run

C++ Przykład drzew AVL

Zalety drzew AVL

  • Wysokość drzewa AVL jest zawsze zrównoważona i nigdy nie przekracza logarytmu N.
  • Przeszukiwanie jest szybsze niż w przypadku zwykłego drzewa poszukiwań binarnych, ponieważ drzewo nie może ulec degeneracji.
  • Samobalansowanie odbywa się automatycznie — nie jest wymagana żadna odbudowa.
  • Wydajność deterministyczna nadaje się do systemów czasu rzeczywistego i indeksów w pamięci.

FAQ

Drzewo AVL to samobalansujące się drzewo poszukiwań binarnych, w którym współczynnik równowagi każdego węzła pozostaje w zakresie {-1, 0, +1}. Rotacje przywracają ten niezmiennik przy każdym wstawieniu lub usunięciu.ping wyszukiwanie, wstawianie i usuwanie z częstością O(log n).

Współczynnik równowagi węzła jest równy wysokości (lewego poddrzewa) minus wysokość (prawego poddrzewa). Wartości muszą mieścić się w zakresie {-1, 0, +1}. Współczynnik równowagi +2 lub -2 sygnalizuje, że wstawienie lub usunięcie węzła spowodowało jego zachwianie równowagi i konieczna jest rotacja.

Cztery obroty to LL, RR, LR i RL. LL to pojedynczy obrót w prawo, RR to pojedynczy obrót w lewo, a LR i RL to podwójne obroty, które łączą jeden obrót na dziecku z przeciwnym obrotem na węźle.

Wstawianie odbywa się zgodnie ze standardową regułą BST, a następnie drzewo wraca do góry, aktualizując wysokość. Jeśli którykolwiek z przodków naruszy zasadę równowagi, jeden pojedynczy lub podwójny obrót przywraca równowagę. Maksymalnie jeden obrót na wstawienie jest potrzebny.

Drzewa AVL są ściśle zbalansowane, a współczynnik równowagi wynosi maksymalnie jeden, co zapewnia szybsze wyszukiwanie. Drzewa czerwono-czarne pozwalają na luźniejszą równowagę, co sprawia, że ​​wstawianie i usuwanie danych jest tańsze, ale wyszukiwanie jest nieco wolniejsze. Bazy danych preferują drzewa czerwono-czarne w przypadku obciążeń wymagających dużej ilości danych do zapisu.

Drzewa AVL obsługują indeksy baz danych w pamięci, metadane systemu plików, kolejki priorytetowe, wyszukiwanie w książce telefonicznej, sprawdzanie pisowni i dowolne obciążenie wymagające deterministycznego wyszukiwania z szybkością O(log n) i przeglądania w kolejności dla zapytań zakresowych.

Tak. Systemy AI wykorzystują drzewa AVL do tabel symboli, uporządkowanych magazynów cech, równoważenia drzewa kd i wyszukiwania najbliższego sąsiedztwa w danych strukturalnych. Stanowią one również podstawę indeksów wyszukiwania z rankingiem w inteligentnych procesach wyszukiwania.

Tak. GitHub Copilot i podobne asystenty AI obsługują procedury wstawiania, usuwania i obracania w C++, Javalub Pythoni generować testy jednostkowe weryfikujące niezmienność współczynnika równowagi dla każdej operacji.

Podsumuj ten post następująco: