Podręcznik

2. Drzewa AVL

2.1. Rotacja i wskaźnik wyważenia

Drzewa AVL są równoważone w taki sposób, by różnica wysokości lewego i prawego poddrzewa dowolnego wynosiła nie więcej niż 1.

Jeśli po wstawieniu (lub usunięciu) węzła, równowaga drzewa zostaje naruszona, to należy je przebudować lokalnie, wykonując odpowiednie rotacje. Istnieją cztery typy rotacji:

Rotacja jednokrotna w prawo – przypadek lewo-lewo (LL),
Rotacja jednokrotna w lewo – przypadek prawo-prawo (RR),
Rotacja lewo-prawo (LR) – najpierw w lewo, potem w prawo,
Rotacja prawo-lewo (RL) – najpierw w prawo, potem w lewo.

Lewa rotacja względem węzła polega na tym, że prawy syn tego węzła (nie może być on równy NULL) wchodzi na jego miejsce, przesuwając ojca w lewo: węzeł-ojciec staje się teraz lewym synem swojego dotychczasowego syna.

Prawa rotacja względem węzła polega na tym, że lewy syn tego węzła (nie może być on równy NULL) wchodzi na jego miejsce, przesuwając ojca w prawo: węzeł-ojciec staje się teraz prawym synem swojego dotychczasowego syna.


#include <iostream>
using namespace std;

// Struktura węzła drzewa AVL
struct Node {
    int key;
    Node* left;
    Node* right;
    int height;

    Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {}
};

// Funkcja pomocnicza: wysokość węzła
int height(Node* node) {
    return node ? node->height : 0;
}

// Maksimum z dwóch wartości
int max(int a, int b) {
    return (a > b) ? a : b;
}

// Obliczanie wskaźnika równowagi węzła
int getBalance(Node* node) {
    if (node == nullptr) return 0;
    return height(node->left) - height(node->right);
}

// Rotacja w lewo
Node* rotateLeft(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    // Rotacja
    y->left = x;
    x->right = T2;

    // Aktualizacja wysokości
    x->height = 1 + max(height(x->left), height(x->right));
    y->height = 1 + max(height(y->left), height(y->right));

    return y;
}

// Rotacja w prawo
Node* rotateRight(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    // Rotacja
    x->right = y;
    y->left = T2;

    // Aktualizacja wysokości
    y->height = 1 + max(height(y->left), height(y->right));
    x->height = 1 + max(height(x->left), height(x->right));

    return x;
}