ALBERO AVL (STRUTTURE DATI)

L'albero AVL è stato inventato da GM Adelson - Velsky e EM Landis nel 1962. L'albero è chiamato AVL in onore dei suoi inventori.

L'AVL Tree può essere definito come un albero di ricerca binario bilanciato in altezza in cui a ciascun nodo è associato un fattore di equilibrio calcolato sottraendo l'altezza del suo sottoalbero destro da quella del suo sottoalbero sinistro.

Si dice che l'albero sia bilanciato se il fattore di equilibrio di ciascun nodo è compreso tra -1 e 1, altrimenti l'albero sarà sbilanciato e dovrà essere bilanciato.

Fattore di equilibrio (k) = altezza (sinistra(k)) - altezza (destra(k))

Se il fattore di equilibrio di qualsiasi nodo è 1, significa che il sottoalbero di sinistra è un livello più alto del sottoalbero di destra.

Se il fattore di equilibrio di qualsiasi nodo è 0, significa che il sottoalbero sinistro e il sottoalbero destro hanno la stessa altezza.

Se il fattore di equilibrio di qualsiasi nodo è -1, significa che il sottoalbero di sinistra è un livello inferiore rispetto al sottoalbero di destra.

Un albero AVL è riportato nella figura seguente. Possiamo vedere che il fattore di equilibrio associato a ciascun nodo è compreso tra -1 e +1. pertanto, è un esempio di albero AVL.

Complessità

Algoritmo	Caso medio	Il caso peggiore
Spazio	SU)	SU)
Ricerca	o(log n)	o(log n)
Inserire	o(log n)	o(log n)
Eliminare	o(log n)	o(log n)

Operazioni sull'albero AVL

Dato che l'albero AVL è anche un albero di ricerca binario, tutte le operazioni vengono eseguite nello stesso modo in cui vengono eseguite in un albero di ricerca binario. La ricerca e l'attraversamento non portano alla violazione della proprietà dell'albero AVL. Tuttavia, l'inserimento e l'eliminazione sono operazioni che possono violare questa proprietà e pertanto devono essere rivisitate.

SN	Operazione	Descrizione
1	Inserimento	L'inserimento nell'albero AVL viene eseguito nello stesso modo in cui viene eseguito in un albero di ricerca binario. Tuttavia, ciò potrebbe portare a una violazione della proprietà dell'albero AVL e pertanto potrebbe essere necessario bilanciare l'albero. L'albero può essere bilanciato applicando rotazioni.
2	Cancellazione	La cancellazione può anche essere eseguita nello stesso modo in cui viene eseguita in un albero di ricerca binario. L'eliminazione può anche disturbare l'equilibrio dell'albero, pertanto vengono utilizzati vari tipi di rotazioni per riequilibrare l'albero.

Perchè l'albero AVL?

L'albero AVL controlla l'altezza dell'albero di ricerca binario impedendogli di essere distorto. Il tempo impiegato per tutte le operazioni in un albero di ricerca binario di altezza h è OH) . Può però essere esteso a SU) se il BST diventa distorto (cioè il caso peggiore). Limitando questa altezza al log n, l'albero AVL impone un limite superiore su ciascuna operazione O(log n) dove n è il numero di nodi.

Rotazioni AVL

Eseguiamo la rotazione nell'albero AVL solo nel caso in cui il Balance Factor sia diverso da -1, 0 e 1 . Esistono fondamentalmente quattro tipi di rotazioni che sono le seguenti:

L Rotazione L: il nodo inserito si trova nel sottoalbero sinistro del sottoalbero sinistro di A
R Rotazione R: il nodo inserito si trova nel sottoalbero destro del sottoalbero destro di A
Rotazione L R: il nodo inserito si trova nel sottoalbero destro del sottoalbero sinistro di A
Rotazione R L: il nodo inserito si trova nel sottoalbero sinistro del sottoalbero destro di A

Dove il nodo A è il nodo il cui Fattore di equilibrio è diverso da -1, 0, 1.

Le prime due rotazioni LL e RR sono rotazioni singole e le due rotazioni successive LR e RL sono rotazioni doppie. Perché un albero sia sbilanciato l'altezza minima deve essere almeno 2, comprendiamo ogni rotazione

Java confronta le stringhe

1. Rotazione RR

Quando BST diventa sbilanciato, a causa dell'inserimento di un nodo nel sottoalbero destro del sottoalbero destro di A, allora eseguiamo la rotazione RR, la rotazione RR è una rotazione antioraria, che viene applicata sul bordo sotto un nodo avente fattore di bilanciamento -2

Nell'esempio sopra, il nodo A ha un fattore di equilibrio -2 perché un nodo C è inserito nel sottoalbero destro di A sottoalbero destro. Eseguiamo la rotazione RR sul bordo sotto A.

2. Rotazione LL

Quando BST diventa sbilanciato, a causa dell'inserimento di un nodo nel sottoalbero sinistro del sottoalbero sinistro di C, allora eseguiamo la rotazione LL, la rotazione LL è la rotazione in senso orario, che viene applicata sul bordo sotto un nodo avente fattore di bilanciamento 2.

Nell'esempio sopra, il nodo C ha un fattore di equilibrio 2 perché un nodo A è inserito nel sottoalbero sinistro del sottoalbero sinistro C. Eseguiamo la rotazione LL sul bordo sotto A.

3. Rotazione LR

Le doppie rotazioni sono leggermente più difficili della rotazione singola, come già spiegato sopra. Rotazione LR = Rotazione RR + Rotazione LL, ovvero la prima rotazione RR viene eseguita sul sottoalbero e poi la rotazione LL viene eseguita sull'albero completo, per albero completo si intende il primo nodo del percorso del nodo inserito il cui fattore di equilibrio è diverso da -1 , 0 o 1.

Cerchiamo di comprendere ogni singolo passaggio molto chiaramente:

Java comparabile

Stato	Azione
	Un nodo B è stato inserito nel sottoalbero destro di A, nel sottoalbero sinistro di C, per cui C è diventato un nodo sbilanciato con fattore di bilanciamento 2. Questo caso è la rotazione L R dove: Il nodo inserito è nel sottoalbero destro del sottoalbero sinistro di C
	Poiché rotazione LR = rotazione RR + LL, quindi RR (in senso antiorario) sul sottoalbero con radice in A viene eseguito per primo. Eseguendo la rotazione RR, node UN , è diventato il sottoalbero sinistro di B .
	Dopo aver eseguito la rotazione RR, il nodo C è ancora sbilanciato, cioè ha un fattore di equilibrio 2, poiché il nodo A inserito è a sinistra di sinistra di C
	Ora eseguiamo la rotazione LL in senso orario sull'intero albero, cioè sul nodo C. nodo C è ora diventato il sottoalbero destro del nodo B, A è il sottoalbero sinistro di B
	Il fattore di equilibrio di ciascun nodo ora è -1, 0 o 1, ovvero BST ora è bilanciato.

4. Rotazione RL

Come già discusso, le doppie rotazioni sono leggermente più difficili della rotazione singola, come già spiegato sopra. Rotazione R L = Rotazione LL + Rotazione RR, ovvero la prima rotazione LL viene eseguita sul sottoalbero e poi la rotazione RR viene eseguita sull'albero completo, per albero completo si intende il primo nodo del percorso del nodo inserito il cui fattore di equilibrio è diverso da -1 , 0 o 1.

Stato	Azione
	Un nodo B è stato inserito nel sottoalbero sinistro di C il sottoalbero destro di UN , per cui A è diventato un nodo sbilanciato con fattore di equilibrio - 2. Questo caso è la rotazione RL dove: Il nodo inserito è nel sottoalbero sinistro del sottoalbero destro di A
	Poiché rotazione RL = rotazione LL + rotazione RR, quindi LL (in senso orario) sul sottoalbero con radice C viene eseguito per primo. Eseguendo la rotazione RR, node C è diventato il sottoalbero destro di B .
	Dopo aver eseguito la rotazione LL, node UN è ancora sbilanciato, cioè ha un fattore di equilibrio -2, a causa del sottoalbero destro del nodo A del sottoalbero destro.
	Ora eseguiamo la rotazione RR (rotazione in senso antiorario) sull'intero albero, cioè sul nodo A. nodo C è ora diventato il sottoalbero destro del nodo B e il nodo A è diventato il sottoalbero sinistro di B.
	Il fattore di equilibrio di ciascun nodo ora è -1, 0 o 1, ovvero BST ora è bilanciato.

D: Costruisci un albero AVL con i seguenti elementi

H, I, J, B, A, E, C, F, D, G, K, L

1. Inserisci H, I, J

Inserendo gli elementi sopra indicati, soprattutto nel caso di H, il BST si sbilancia in quanto il Balance Factor di H è -2. Poiché il BST è inclinato a destra, eseguiremo la rotazione RR sul nodo H.

L’albero di bilancio risultante è:

2. Inserisci B, A

Inserendo gli elementi di cui sopra, specialmente nel caso di A, il BST diventa sbilanciato poiché il fattore di equilibrio di H e I è 2, consideriamo il primo nodo dell'ultimo nodo inserito, ovvero H. Poiché il BST di H è distorto a sinistra, eseguiremo la rotazione LL sul nodo H.

L’albero di bilancio risultante è:

3. Inserisci E

Inserendo E, BST si sbilancia poiché il Fattore di Equilibrio di I è 2, poiché se viaggiamo da E a I troviamo che è inserito nel sottoalbero sinistro del sottoalbero destro di I, eseguiremo la rotazione LR sul nodo I. LR = Rotazione RR + LL

3 a) Per prima cosa eseguiamo la rotazione RR sul nodo B

L'albero risultante dopo la rotazione RR è:

3b) Eseguiamo prima la rotazione LL sul nodo I

L'albero bilanciato risultante dopo la rotazione LL è:

4. Inserisci C, F, D

affettare l'array Java

Inserendo C, F, D, BST diventa sbilanciato in quanto il Fattore di Equilibrio di B e H è -2, poiché se viaggiamo da D a B troviamo che è inserito nel sottoalbero destro del sottoalbero sinistro di B, eseguiremo RL Rotazione sul nodo I. RL = LL + rotazione RR.

4a) Eseguiamo prima la rotazione LL sul nodo E

L'albero risultante dopo la rotazione LL è:

4b) Eseguiamo quindi la rotazione RR sul nodo B

L'albero bilanciato risultante dopo la rotazione RR è:

5. Inserisci G

Inserendo G, BST si sbilancia poiché il Fattore di Equilibrio di H è 2, poiché se viaggiamo da G a H, troviamo che è inserito nel sottoalbero sinistro del sottoalbero destro di H, eseguiremo la rotazione LR sul nodo I. LR = rotazione RR + LL.

5 a) Eseguiamo innanzitutto la rotazione RR sul nodo C

L'albero risultante dopo la rotazione RR è:

5 b) Eseguiamo quindi la rotazione LL sul nodo H

L'albero bilanciato risultante dopo la rotazione LL è:

6. Inserisci K

Inserendo K, BST diventa sbilanciato poiché il fattore di bilanciamento di I è -2. Poiché il BST è inclinato a destra da I a K, eseguiremo la rotazione RR sul nodo I.