Albero AVL
Ultimo aggiornamento
Un albero AVL è un albero binario di ricerca autobilanciato. Funziona come un normale BST, ma dopo ogni inserimento controlla il fattore di bilanciamento di ogni antenato, cioè la differenza di altezza tra il sottoalbero sinistro e quello destro. Se un nodo diventa sbilanciato (differenza maggiore di 1), esegue delle rotazioni per ripristinare l'equilibrio. Premi play qui sopra per vedere i valori inseriti e l'albero che ruota per tornare in forma.
Dato che non lascia mai l'albero pendere più di poco da un lato, un albero AVL garantisce un'altezza O(log n), quindi ricerca, inserimento ed eliminazione sono sempre O(log n), anche con un input ordinato che rovinerebbe un BST semplice. Il costo sono le rotazioni extra e la gestione delle altezze a ogni inserimento.
Complessità temporale e spaziale
| Operazione | Complessità | Note |
|---|---|---|
| Ricerca | O(log n) | L'altezza è sempre circa 1,44 log n |
| Inserimento | O(log n) | Più O(1) rotazioni |
| Eliminazione | O(log n) | Più O(log n) rotazioni |
| Spazio | O(n) | Un campo altezza per nodo |
I quattro casi di rotazione
| Caso | Sbilanciamento | Correzione |
|---|---|---|
| Sinistra-Sinistra | Pesante a sinistra del figlio sinistro | Una rotazione a destra |
| Destra-Destra | Pesante a destra del figlio destro | Una rotazione a sinistra |
| Sinistra-Destra | Pesante a destra del figlio sinistro | Rotazione a sinistra, poi a destra |
| Destra-Sinistra | Pesante a sinistra del figlio destro | Rotazione a destra, poi a sinistra |
Esempio svolto
Inserimento di [10, 20, 30, 40, 50, 25] un valore alla volta:
| Passo | Struttura | Azione |
|---|---|---|
Inserisci 10 | 10 | Il primo nodo diventa la radice; bilanciato |
Inserisci 20 | 10(_, 20) | Va a destra di 10; ancora bilanciato |
Inserisci 30 | 20(10, 30) | Caso Destra-Destra in 10, quindi una rotazione a sinistra porta 20 alla radice |
Inserisci 40 | 20(10, 30(_, 40)) | Va a destra di 30; ogni fattore di bilanciamento resta entro ±1 |
Inserisci 50 | 20(10, 40(30, 50)) | Caso Destra-Destra in 30, quindi una rotazione a sinistra in 30 fa salire 40 |
Inserisci 25 | 30(20(10, 25), 40(_, 50)) | Caso Destra-Sinistra in 20: ruota a destra il sottoalbero di 40, poi ruota a sinistra 20 |
Quando usare un albero AVL
| Usalo quando | Evitalo quando |
|---|---|
| Le ricerche superano di gran lunga gli inserimenti e vuoi l'altezza più bassa possibile | Dominano inserimenti ed eliminazioni: le rotazioni e i ribilanciamenti extra costano più di quelli di un albero rosso-nero |
Ti serve un caso peggiore O(log n) garantito, anche con input ostili o ordinati | Basterebbe una semplice tabella hash: non ti servono visite ordinate né query su intervalli |
| Ti servono operazioni ordinate: visita in ordine, predecessore/successore, query su intervalli | L'insieme di dati è minuscolo: un BST semplice o un array ordinato è più semplice e abbastanza veloce |
| I dati possono arrivare già ordinati, cosa che trasformerebbe un BST non bilanciato in una lista concatenata | Non puoi permetterti la memoria extra del campo altezza per nodo in un ambiente molto limitato |
Codice AVL Tree
Un'implementazione di AVL Tree pulita ed eseguibile in Python, JavaScript, Java, C++, C. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice AVL Tree in Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 self.height = 17
8
9def height(node):10 return node.height if node else 011
12
13def update(node):14 node.height = 1 + max(height(node.left), height(node.right))15
16
17def rotate_right(y):18 x = y.left19 y.left = x.right20 x.right = y21 update(y)22 update(x)23 return x24
25
26def rotate_left(x):27 y = x.right28 x.right = y.left29 y.left = x30 update(x)31 update(y)32 return y33
34
35def insert(node, key):36 if node is None:37 return Node(key)38 if key < node.key:39 node.left = insert(node.left, key)40 else:41 node.right = insert(node.right, key)42 update(node)43 balance = height(node.left) - height(node.right)44 # Four imbalance cases: LL, RR, LR, RL45 if balance > 1 and key < node.left.key:46 return rotate_right(node)47 if balance < -1 and key > node.right.key:48 return rotate_left(node)49 if balance > 1:50 node.left = rotate_left(node.left)51 return rotate_right(node)52 if balance < -1:53 node.right = rotate_right(node.right)54 return rotate_left(node)55 return node56
57
58def inorder(node):59 if node is None:60 return []61 return inorder(node.left) + [node.key] + inorder(node.right)62
63
64root = None65for key in [10, 20, 30, 40, 50, 25]:66 root = insert(root, key)67
68print("Inorder:", inorder(root))69print("Root:", root.key, "| tree height:", root.height)Codice AVL Tree in JavaScript
JavaScript
1class Node {2 constructor(key) {3 this.key = key;4 this.left = null;5 this.right = null;6 this.height = 1;7 }8}9
10const height = (n) => (n ? n.height : 0);11const update = (n) => {12 n.height = 1 + Math.max(height(n.left), height(n.right));13};14const balance = (n) => height(n.left) - height(n.right);15
16function rotateRight(y) {17 const x = y.left;18 y.left = x.right;19 x.right = y;20 update(y);21 update(x);22 return x;23}24
25function rotateLeft(x) {26 const y = x.right;27 x.right = y.left;28 y.left = x;29 update(x);30 update(y);31 return y;32}33
34function insert(node, key) {35 if (!node) return new Node(key);36 if (key < node.key) node.left = insert(node.left, key);37 else node.right = insert(node.right, key);38 update(node);39 const b = balance(node);40 // Four rebalancing cases: LL, RR, LR, RL41 if (b > 1 && key < node.left.key) return rotateRight(node);42 if (b < -1 && key > node.right.key) return rotateLeft(node);43 if (b > 1) {44 node.left = rotateLeft(node.left);45 return rotateRight(node);46 }47 if (b < -1) {48 node.right = rotateRight(node.right);49 return rotateLeft(node);50 }51 return node;52}53
54function inorder(node, out = []) {55 if (!node) return out;56 inorder(node.left, out);57 out.push(node.key);58 inorder(node.right, out);59 return out;60}61
62let root = null;63for (const key of [10, 20, 30, 40, 50, 25]) root = insert(root, key);64console.log("Root after rebalancing:", root.key);65console.log("Inorder:", inorder(root).join(" "));Codice AVL Tree in Java
Java
1public class Main {2 static class Node {3 int key, height = 1;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static int height(Node n) { return n == null ? 0 : n.height; }9 static int balance(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }10 static void update(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }11
12 static Node rotateRight(Node y) {13 Node x = y.left;14 y.left = x.right;15 x.right = y;16 update(y); update(x);17 return x;18 }19
20 static Node rotateLeft(Node x) {21 Node y = x.right;22 x.right = y.left;23 y.left = x;24 update(x); update(y);25 return y;26 }27
28 static Node insert(Node node, int key) {29 if (node == null) return new Node(key);30 if (key < node.key) node.left = insert(node.left, key);31 else node.right = insert(node.right, key);32 update(node);33 int b = balance(node);34 // Four imbalance cases: LL, RR, LR, RL35 if (b > 1 && key < node.left.key) return rotateRight(node);36 if (b < -1 && key > node.right.key) return rotateLeft(node);37 if (b > 1) { node.left = rotateLeft(node.left); return rotateRight(node); }38 if (b < -1) { node.right = rotateRight(node.right); return rotateLeft(node); }39 return node;40 }41
42 static void inorder(Node n, StringBuilder sb) {43 if (n == null) return;44 inorder(n.left, sb);45 sb.append(n.key).append(" ");46 inorder(n.right, sb);47 }48
49 public static void main(String[] args) {50 Node root = null;51 int[] keys = {10, 20, 30, 40, 50, 25};52 for (int k : keys) root = insert(root, k);53 StringBuilder sb = new StringBuilder();54 inorder(root, sb);55 System.out.println("Inorder: " + sb.toString().trim());56 System.out.println("Root after rebalancing: " + root.key + " (height " + root.height + ")");57 }58}Codice AVL Tree in C++
C++
1#include <algorithm>2#include <iostream>3
4struct Node {5 int value;6 int height = 1;7 Node* left = nullptr;8 Node* right = nullptr;9 explicit Node(int v) : value(v) {}10};11
12int height(const Node* n) { return n ? n->height : 0; }13int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }14void updateHeight(Node* n) {15 n->height = 1 + std::max(height(n->left), height(n->right));16}17
18Node* rotateRight(Node* y) {19 Node* x = y->left;20 y->left = x->right;21 x->right = y;22 updateHeight(y);23 updateHeight(x);24 return x;25}26
27Node* rotateLeft(Node* x) {28 Node* y = x->right;29 x->right = y->left;30 y->left = x;31 updateHeight(x);32 updateHeight(y);33 return y;34}35
36Node* insert(Node* node, int value) {37 if (node == nullptr) return new Node(value);38 if (value < node->value) node->left = insert(node->left, value);39 else node->right = insert(node->right, value);40 updateHeight(node);41 int balance = balanceFactor(node);42 // Four rebalancing cases: LL, RR, LR, RL43 if (balance > 1 && value < node->left->value) return rotateRight(node);44 if (balance < -1 && value > node->right->value) return rotateLeft(node);45 if (balance > 1) {46 node->left = rotateLeft(node->left);47 return rotateRight(node);48 }49 if (balance < -1) {50 node->right = rotateRight(node->right);51 return rotateLeft(node);52 }53 return node;54}55
56void inorder(const Node* n) {57 if (n == nullptr) return;58 inorder(n->left);59 std::cout << n->value << "(h" << n->height << ") ";60 inorder(n->right);61}62
63int main() {64 Node* root = nullptr;65 for (int value : {10, 20, 30, 40, 50, 25}) root = insert(root, value);66 std::cout << "Root after rebalancing: " << root->value << "\n";67 std::cout << "In-order: ";68 inorder(root);69 std::cout << "\n";70 return 0;71}Codice AVL Tree in C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value, height;6 struct Node* left;7 struct Node* right;8} Node;9
10int height(const Node* n) { return n ? n->height : 0; }11int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }12int maxInt(int a, int b) { return a > b ? a : b; }13
14Node* newNode(int value) {15 Node* n = calloc(1, sizeof(Node));16 n->value = value;17 n->height = 1;18 return n;19}20
21void updateHeight(Node* n) {22 n->height = 1 + maxInt(height(n->left), height(n->right));23}24
25Node* rotateRight(Node* y) {26 Node* x = y->left;27 y->left = x->right;28 x->right = y;29 updateHeight(y);30 updateHeight(x);31 return x;32}33
34Node* rotateLeft(Node* x) {35 Node* y = x->right;36 x->right = y->left;37 y->left = x;38 updateHeight(x);39 updateHeight(y);40 return y;41}42
43Node* insert(Node* node, int value) {44 if (node == NULL) return newNode(value);45 if (value < node->value) node->left = insert(node->left, value);46 else node->right = insert(node->right, value);47 updateHeight(node);48 int balance = balanceFactor(node);49 // Four rebalancing cases: LL, RR, LR, RL50 if (balance > 1 && value < node->left->value) return rotateRight(node);51 if (balance < -1 && value > node->right->value) return rotateLeft(node);52 if (balance > 1) {53 node->left = rotateLeft(node->left);54 return rotateRight(node);55 }56 if (balance < -1) {57 node->right = rotateRight(node->right);58 return rotateLeft(node);59 }60 return node;61}62
63void inorder(const Node* n) {64 if (n == NULL) return;65 inorder(n->left);66 printf("%d(h%d) ", n->value, n->height);67 inorder(n->right);68}69
70int main(void) {71 int values[] = {10, 20, 30, 40, 50, 25};72 Node* root = NULL;73 for (int i = 0; i < 6; i++) root = insert(root, values[i]);74 printf("Root after rebalancing: %d\n", root->value);75 printf("In-order: ");76 inorder(root);77 printf("\n");78 return 0;79}Domande frequenti sull'albero AVL
Cos'è il fattore di bilanciamento in un albero AVL?
Il fattore di bilanciamento di un nodo è l'altezza del suo sottoalbero sinistro meno l'altezza del sottoalbero destro. Un albero AVL mantiene il fattore di ogni nodo a -1, 0 o +1; se un inserimento lo porta fuori da questo intervallo, una rotazione ripristina l'equilibrio.
Qual è la differenza tra un albero AVL e un albero rosso-nero?
Entrambi sono BST autobilanciati con operazioni
O(log n). Gli alberi AVL sono bilanciati in modo più rigido, quindi le ricerche sono leggermente più veloci, ma possono fare più rotazioni negli inserimenti e nelle eliminazioni. Gli alberi rosso-neri sono bilanciati in modo più lasco e fanno meno rotazioni: per questo molte librerie standard li usano per mappe e insiemi.Perché usare un albero AVL invece di un semplice albero binario di ricerca?
Un BST semplice può degradare a operazioni
O(n) se i valori arrivano in ordine, formando una catena sbilanciata. Un albero AVL ruota per restare bilanciato e garantisce altezza e operazioni O(log n) qualunque sia l'ordine di inserimento.Per l'indice di un database è meglio un albero AVL o un albero rosso-nero?
Dipende dal carico di lavoro. Gli alberi AVL sono bilanciati in modo più rigido, quindi vincono quando dominano le letture e vuoi i percorsi di ricerca più corti possibili. Però la maggior parte dei database e delle librerie dei linguaggi sceglie gli alberi rosso-neri (o i B-tree), perché ribilanciano con meno rotazioni nei carichi con molte scritture, e questo conta di più quando inserimenti ed eliminazioni sono frequenti.
Quante rotazioni servono per un singolo inserimento in un AVL?
Al massimo una rotazione, semplice oppure doppia (in due passaggi), basta per ribilanciare l'albero dopo l'inserimento di un valore. Questo perché un inserimento aumenta l'altezza di un sottoalbero al massimo di uno, quindi basta una sola correzione sull'antenato sbilanciato più in basso. L'eliminazione è diversa: può richiedere fino a
O(log n) rotazioni, perché il ribilanciamento si propaga verso la radice.Devo aggiornare le altezze dei nodi dopo ogni rotazione?
Sì. Un errore comune è ruotare correttamente i puntatori ma dimenticare di ricalcolare l'altezza dei due nodi coinvolti. Dopo ogni rotazione devi aggiornare prima l'altezza del nodo che scende e poi quella del nodo che sale, perché l'altezza del nodo promosso dipende dai suoi nuovi figli. Se salti questo passaggio, i fattori di bilanciamento restano vecchi e rovinano le decisioni di ribilanciamento successive.
Risorse correlate
Altre visualizzazioni
