AVL-fa
Kiejtés
- IPA: [ ˈɒvlfɒ]
Főnév
- (matematika, algoritmusok) önkiegyensúlyozó bináris keresőfa
Az AVL-fa egy kiegyensúlyozott bináris keresőfa, amely biztosítja, hogy az egyes csomópontokhoz tartozó bal és jobb részfák magasságának különbsége legfeljebb 1 legyen. Az AVL-fa nevét az alkotókról, Adelson-Velsky és Landis matematikusokról kapta.
Tulajdonságok
- Magassági különbség (balance factor):
- Egy csomópont kiegyensúlyozottsági faktora a bal és jobb részfa magasságának különbsége: [ = - ]
- Értéke lehet: (-1, 0, 1).
- Kiegyensúlyozottság fenntartása:
- Ha a beszúrás vagy törlés miatt egy csomópont kiegyensúlyozottsági faktora (-1, 0, 1)-en kívülre kerül, a fa kiegyensúlyozatlanná válik, és forgatásokkal helyre kell állítani.
- Rotációk (forgatások):
- Bal forgatás (Left Rotation): Ha a jobb részfa túl magas.
- Jobb forgatás (Right Rotation): Ha a bal részfa túl magas.
- Bal-jobb forgatás (Left-Right Rotation): Ha a bal részfa jobb gyereke okoz kiegyensúlyozatlanságot.
- Jobb-bal forgatás (Right-Left Rotation): Ha a jobb részfa bal gyereke okoz kiegyensúlyozatlanságot.
- Időkomplexitás:
- Beszúrás, törlés, keresés: (O(n)).
Pszeudokód
Beszúrás
Insert(node, key):
ha node üres:
hozz létre egy új csomópontot a key értékkel
ha key < node.key:
node.bal = Insert(node.bal, key)
különben:
node.jobb = Insert(node.jobb, key)
frissítsd a node magasságát
balance = balance_factor(node)
ha balance > 1 és key < node.bal.key:
térj vissza jobb_forgatás(node)
ha balance < -1 és key > node.jobb.key:
térj vissza bal_forgatás(node)
ha balance > 1 és key > node.bal.key:
node.bal = bal_forgatás(node.bal)
térj vissza jobb_forgatás(node)
ha balance < -1 és key < node.jobb.key:
node.jobb = jobb_forgatás(node.jobb)
térj vissza bal_forgatás(node)
térj vissza node
Forgatás
Bal_forgatás(z):
y = z.jobb
T2 = y.bal
y.bal = z
z.jobb = T2
frissítsd z és y magasságát
térj vissza y
Jobb_forgatás(z):
y = z.bal
T3 = y.jobb
y.jobb = z
z.bal = T3
frissítsd z és y magasságát
térj vissza y
Python implementáció
class AVLNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def get_height(self, node):
return node.height if node else 0
def get_balance(self, node):
return self.get_height(node.left) - self.get_height(node.right) if node else 0
def right_rotate(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
return y
def left_rotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
return y
def insert(self, node, key):
if not node:
return AVLNode(key)
if key < node.key:
node.left = self.insert(node.left, key)
else:
node.right = self.insert(node.right, key)
node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
balance = self.get_balance(node)
if balance > 1 and key < node.left.key:
return self.right_rotate(node)
if balance < -1 and key > node.right.key:
return self.left_rotate(node)
if balance > 1 and key > node.left.key:
node.left = self.left_rotate(node.left)
return self.right_rotate(node)
if balance < -1 and key < node.right.key:
node.right = self.right_rotate(node.right)
return self.left_rotate(node)
return node
def pre_order(self, root):
if not root:
return
print(root.key, end=" ")
self.pre_order(root.left)
self.pre_order(root.right)
# Példa használat
tree = AVLTree()
root = None
keys = [10, 20, 30, 40, 50, 25]
for key in keys:
root = tree.insert(root, key)
print("Preorder bejárás:")
tree.pre_order(root)
Kimenet:
Preorder bejárás: 30 20 10 25 40 50
C++ implementáció
#include <iostream>
using namespace std;
struct AVLNode {
int key;
AVLNode* left;
AVLNode* right;
int height;
AVLNode(int value) : key(value), left(nullptr), right(nullptr), height(1) {}
};
class AVLTree {
public:
int get_height(AVLNode* node) {
return node ? node->height : 0;
}
int get_balance(AVLNode* node) {
return node ? get_height(node->left) - get_height(node->right) : 0;
}
AVLNode* right_rotate(AVLNode* z) {
AVLNode* y = z->left;
AVLNode* T3 = y->right;
y->right = z;
z->left = T3;
z->height = 1 + max(get_height(z->left), get_height(z->right));
y->height = 1 + max(get_height(y->left), get_height(y->right));
return y;
}
AVLNode* left_rotate(AVLNode* z) {
AVLNode* y = z->right;
AVLNode* T2 = y->left;
y->left = z;
z->right = T2;
z->height = 1 + max(get_height(z->left), get_height(z->right));
y->height = 1 + max(get_height(y->left), get_height(y->right));
return y;
}
AVLNode* insert(AVLNode* node, int key) {
if (!node)
return new AVLNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
node->height = 1 + max(get_height(node->left), get_height(node->right));
int balance = get_balance(node);
if (balance > 1 && key < node->left->key)
return right_rotate(node);
if (balance < -1 && key > node->right->key)
return left_rotate(node);
if (balance > 1 && key > node->left->key) {
node->left = left_rotate(node->left);
return right_rotate(node);
}
if (balance < -1 && key < node->right->key) {
node->right = right_rotate(node->right);
return left_rotate(node);
}
return node;
}
void pre_order(AVLNode* root) {
if (!root) return;
cout << root->key << " ";
pre_order(root->left);
pre_order(root->right);
}
};
int main() {
AVLTree tree;
AVLNode* root = nullptr;
int keys[] = {10, 20, 30, 40, 50, 25};
for (int key : keys) {
root = tree.insert(root, key);
}
cout << "Preorder bejárás: ";
tree.pre_order(root);
cout << endl;
return 0;
}
Kimenet:
Preorder bejárás: 30 20 10 25 40 50
Összegzés
Előnyök:
- Kiegyensúlyozottság: Garantáltan (O(n)) magasság.
- Hatékonyság: Gyors beszúrás, törlés, keresés.
Hátrányok:
- Komplexitás: Több számítás szükséges a kiegyensúlyozás fenntartásához.
- Nem optimális memóriában: További mutatókat és magassági értékeket kell tárolni.
Az AVL-fa kiváló választás olyan alkalmazásokhoz, ahol garantáltan kiegyensúlyozott fa szükséges.