AVL tree
Főnév
Az AVL fa (Adelson-Velsky és Landis fa) egy kiegyensúlyozott bináris keresőfa (BST), amelyet 1962-ben két orosz matematikus, G.M. Adelson-Velsky és E.M. Landis alkotott meg. Az AVL fa azon alapul, hogy biztosítja, hogy a fa minden csomópontjának bal és jobb al-fái közötti magasságkülönbség nem haladhatja meg az 1-et. Az AVL fa tehát kiegyensúlyozott, ami azt jelenti, hogy a fa műveletei (keresés, beszúrás, törlés) időkomplexitása O(log n), ahol n a fa elemeinek száma.
A C++ nyelvben az AVL fa lehetőséget ad arra, hogy gyors keresést, beszúrást és törlést végezzünk úgy, hogy közben fenntartjuk a fa kiegyensúlyozottságát.
AVL Fa Szerkezete:
A hagyományos bináris keresőfa (BST) egy olyan adatstruktúra, amelyben minden csomópontnak legfeljebb két gyereke van: egy bal és egy jobb gyermek. A bal gyermek mindig kisebb, a jobb gyermek pedig nagyobb, mint a szülő csomópont. Az AVL fa ezen felül egy extra tulajdonsággal bír: minden csomópontban tárolva van egy magasságérték, amely azt jelzi, hogy mekkora a csomópont alatti fa legnagyobb magassága.
Az AVL fa lényege, hogy a különböző szinteken elhelyezkedő csomópontok közötti magasságkülönbség nem haladhatja meg az 1-et, azaz minden csomópont magasságkülönbsége a bal és jobb al-fák között legfeljebb 1 lehet.
Magasság különbség és kiegyensúlyozás:
Az AVL fák sajátossága, hogy a beszúrás és a törlés után a fa kiegyensúlyozása szükséges lehet. Ez a balra forgatás, jobbra forgatás vagy ezek kombinációja segítségével történhet, hogy fenntartsuk a fenti tulajdonságot.
Az AVL Fa Műveletei:
Keresés (Search): Az AVL fa keresési művelete alapvetően megegyezik a szokásos bináris keresőfák keresésével. A fa bal oldalán keresve a kisebb, jobb oldalán pedig a nagyobb értékeket találjuk. A keresés eredménye O(log n) időben elérhető, mivel a fa kiegyensúlyozott.
Beszúrás (Insert): Az új elem beszúrása során először a megfelelő helyre kell helyezni az új elemet a fa sorrendje alapján. Ezt követően ellenőrizzük a fa kiegyensúlyozottságát, és ha szükséges, elvégezzük a megfelelő forgatásokat (balra vagy jobbra), hogy a fa újra kiegyensúlyozott legyen.
Törlés (Delete): Az elem törlésénél hasonlóan először meg kell találni a törlendő elemet, majd azt eltávolítani a fából. Ezt követően ellenőrizzük, hogy a fa továbbra is kiegyensúlyozott maradt-e, és ha nem, akkor szükség esetén alkalmazzuk a megfelelő forgatásokat.
Balra és jobbra forgatás (Left and Right Rotations):
- Balra forgatás (Left Rotation): Ez akkor szükséges, amikor a fa jobb oldala túlságosan magas. A forgatás során a jobb gyermek a szülő csomóponttá válik, és annak bal gyermeke a bal oldali ágra kerül.
- Jobbra forgatás (Right Rotation): Ez akkor szükséges, amikor a fa bal oldala túlságosan magas. Ilyenkor a bal gyermek válik szülővé, és annak jobb gyermeke a jobb oldalra kerül.
Mindkét forgatás célja a fa kiegyensúlyozása és annak biztosítása, hogy minden csomópont bal és jobb al-fái közötti magasságkülönbsége ne haladja meg az 1-et.
C++ Kód Példa - AVL Fa Implementáció:
#include <iostream>
using namespace std;
// Csomópont struktúra
struct Node {
int data;
Node* left;
Node* right;
int height;
};
// Segédfunkciók a magasság és a max függvényekhez
int height(Node* N) {
if (N == nullptr) {
return 0;
}
return N->height;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
// Balra és jobbra forgatás
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x;
}
Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y;
}
// Egyensúlyi faktort számol
int getBalance(Node* N) {
if (N == nullptr) {
return 0;
}
return height(N->left) - height(N->right);
}
// Új csomópont beszúrása
Node* insert(Node* node, int data) {
if (node == nullptr) {
Node* newNode = new Node();
newNode->data = data;
newNode->left = newNode->right = nullptr;
newNode->height = 1; // Új csomópont magassága
return newNode;
}
if (data < node->data) {
node->left = insert(node->left, data);
} else if (data > node->data) {
node->right = insert(node->right, data);
} else {
return node; // Az érték már benne van
}
node->height = 1 + max(height(node->left), height(node->right));
int balance = getBalance(node);
// Balra forgatás
if (balance > 1 && data < node->left->data) {
return rightRotate(node);
}
// Jobbra forgatás
if (balance < -1 && data > node->right->data) {
return leftRotate(node);
}
// Bal-jobb forgatás
if (balance > 1 && data > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Jobb-bal forgatás
if (balance < -1 && data < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// Inorder kiírás
void inorder(Node* root) {
if (root != nullptr) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
int main() {
Node* root = nullptr;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 25);
root = insert(root, 5);
cout << "Inorder traversal of the constructed AVL tree is: ";
inorder(root);
return 0;
}
A kód magyarázata:
- A
Nodestruktúra a fa csomópontjait reprezentálja, ahol tároljuk az adatokat, a bal és jobb gyermeket, valamint a csomópont magasságát. - A
heightésmaxsegédfunkciók a fa magasságának meghatározásához szükségesek. - A
rightRotateésleftRotatefüggvények végzik el a szükséges forgatásokat, hogy fenntartsák a fa kiegyensúlyozottságát. - Az
insertfüggvény a megfelelő helyre szúrja be az új adatot, majd ellenőrzi és szükség esetén kiegyensúlyozza a fát. - Az
inorderfüggvény az AVL fa elemeit inorder sorrendben írja ki.
Összegzés:
Az AVL fa egy hatékony adatstruktúra, amely biztosítja a gyors keresést és módosítást a fa kiegyensúlyozottságának fenntartásával. A C++ példánkban megvalósított AVL fa implementáció bemutatja, hogyan lehet alkalmazni a forgatásokat és az egyensúlyozást, hogy a fa műveletei O(log n) időkomplexitásúak legyenek. Az AVL fa ideális megoldás olyan alkalmazások számára, ahol a gyors adatkeresés és a dinamikus változtatások kulcsfontosságúak.