Podręcznik: Drzewa AVL

2. Drzewa AVL

Drzewo AVL to jedna z najstarszych i najbardziej klasycznych struktur danych typu drzewo binarnego wyszukiwania (BST). Jego główną cechą jest samoczynne utrzymywanie zrównoważonej wysokości. Zostało zaproponowane przez dwóch radzieckich matematyków: G.M. Adelsona-Welskiego i E.M. Landisa w 1962 roku. Nazwa AVL pochodzi od pierwszych liter ich nazwisk.

Widzimy, że w zależności od kolejności wstawiania węzłów do drzewa możemy uzyskać inną wysokość drzewa, a więc liczbę poziomów od korzenia do liści.
Dla każdego węzła drzewa AVL definiujemy tzw. balance factor, czyli różnicę wysokości jego lewego i prawego poddrzewa:

$balanceFactor \left( węzeł \right) = wysokosc \left( lewe poddrzewo \right)−wysokosc \left(prawe poddrzewo\right)$

Dopuszczalne wartości:

–1 – prawe poddrzewo jest wyższe o 1,
0 – oba poddrzewa mają tę samą wysokość,
+1 – lewe poddrzewo jest wyższe o 1.

Jeśli wynik wychodzi spoza przedziału <–1;1 >, to znaczy, że drzewo w tym miejscu jest niezrównoważone, i trzeba wykonać odpowiednią rotację. Poniżej przedstawiono kod funkcji do wyznaczania wskaźnika niewyważenia.


int height(Node* node) {
    if (node == nullptr) return 0;
    return node->height;
}

int getBalance(Node* node) {
    if (node == nullptr) return 0;
    return height(node->left) - height(node->right);
}