UN Albero AVL definito autobilanciante La differenza tra le altezze del sottoalbero sinistro e del sottoalbero destro per qualsiasi nodo è nota come fattore di equilibrio del nodo.

L'albero AVL prende il nome dai suoi inventori, Georgy Adelson-Velsky ed Evgenii Landis, che lo pubblicarono nel loro articolo del 1962 Un algoritmo per l'organizzazione delle informazioni.

Esempio di alberi AVL:

Albero AVL

L'albero sopra è AVL perché le differenze tra le altezze dei sottoalberi sinistro e destro per ogni nodo sono inferiori o uguali a 1.

Operazioni su un albero AVL:

• Inserimento
• Cancellazione
• Ricerca [È simile ad eseguire una ricerca in BST]

Rotazione dei sottoalberi in un albero AVL:

Un albero AVL può ruotare in uno dei quattro modi seguenti per mantenersi in equilibrio:

Rotazione a sinistra :

Quando un nodo viene aggiunto al sottoalbero destro del sottoalbero destro, se l'albero perde l'equilibrio, eseguiamo una singola rotazione a sinistra.

Rotazione a sinistra nell'albero AVL

Rotazione destra :

stringa.valoredi

Se un nodo viene aggiunto al sottoalbero sinistro del sottoalbero sinistro, l'albero AVL potrebbe sbilanciarsi, eseguiamo una singola rotazione a destra.

Rotazione a destra nell'albero AVL

Rotazione sinistra-destra :

Una rotazione sinistra-destra è una combinazione in cui avviene la prima rotazione a sinistra dopo l'esecuzione della rotazione a destra.

Rotazione sinistra-destra nell'albero AVL

Rotazione destra-sinistra :

Una rotazione destra-sinistra è una combinazione in cui avviene la prima rotazione destra dopo l'esecuzione della rotazione sinistra.

Rotazione destra-sinistra nell'albero AVL

Applicazioni dell'albero AVL:

1. Viene utilizzato per indicizzare enormi record in un database e anche per effettuare ricerche efficienti al suo interno.
2. Per tutti i tipi di raccolte in memoria, inclusi set e dizionari, vengono utilizzati gli alberi AVL.
3. Applicazioni di database, dove gli inserimenti e le cancellazioni sono meno comuni ma sono necessarie frequenti ricerche di dati
4. Software che necessita di ricerca ottimizzata.
5. Viene applicato in aree aziendali e giochi di trama.

Vantaggi dell'albero AVL:

1. Gli alberi AVL possono autobilanciarsi.
2. Sicuramente non è distorto.
3. Fornisce ricerche più veloci rispetto agli alberi rosso-neri
4. Migliore complessità temporale della ricerca rispetto ad altri alberi come l'albero binario.
5. L'altezza non può superare log(N), dove N è il numero totale di nodi nell'albero.

Svantaggi dell'albero AVL:

1. È difficile da implementare.
2. Ha fattori costanti elevati per alcune operazioni.
3. Meno utilizzato rispetto agli alberi Rosso-Neri.
4. A causa del suo equilibrio piuttosto rigido, gli alberi AVL forniscono complicate operazioni di inserimento e rimozione man mano che vengono eseguite più rotazioni.
5. Richiedi più elaborazione per il bilanciamento.

Articoli Correlati:

• Introduzione agli alberi di ricerca binari: tutorial sulla struttura dei dati e sugli algoritmi
• Inserimento in un albero AVL
• Cancellazione in un albero AVL