Introduzione all'albero AVL nella struttura dei dati
L'albero AVL nella struttura dei dati si riferisce ad Adelson, Velski e Landis Tree. Questa è una versione migliorata dell'albero di ricerca binario. Ha tutte le caratteristiche dell'albero binario di ricerca ma differisce solo perché mantengono una differenza tra l'altezza dell'albero secondario sinistro e l'albero secondario destro e assicura anche che il suo valore sia <= 1 nell'albero, questo è noto come Balance Fattore.
Balance Factor = height(left-subtree) − height(right-subtree)
Ad esempio: considerare i seguenti alberi
Nell'esempio sopra, l'altezza dell'albero secondario destro = 2 e sinistra = 3, quindi BF = 2 che è <= 1, quindi si dice che l'albero sia bilanciato.
Perché abbiamo bisogno di un albero AVL in DS?
Mentre lavoriamo con l'albero di ricerca binario, ci imbattiamo in uno scenario in cui gli elementi sono in ordine. In tali casi tutti gli elementi dell'array sono disposti su un lato della radice, questo porta ad un aumento della complessità temporale della ricerca di un elemento in un array e la complessità diventa-O (n) cioè la complessità del caso peggiore dell'albero . Per risolvere tali problemi e ridurre i tempi di ricerca, gli alberi AVL sono stati inventati da Adelson, Velski & Landis.
Esempio:
Nella figura sopra, Altezza della sottostruttura sinistra = 3 era come
Altezza della sottostruttura destra = 0
Pertanto, Balance Factor = 3-0 = 3. Pertanto la ricerca di un elemento in tale albero ha una O (n) di complessità che è simile alla ricerca lineare. Per evitare quella complessa ricerca, è stato introdotto l'albero AVL in cui tutti i nodi dell'albero devono essere mantenuti
fattore di bilanciamento <= 1, altrimenti devono essere eseguite varie tecniche di rotazione per bilanciare tale albero.
Struct AVLNode
(
int data;
struct AVLNode *left, *right;
int ball factor;
);
Tipi di rotazioni
Quando il fattore di bilanciamento per l'albero non soddisfa la condizione <= 1, è necessario eseguire delle rotazioni su di essi per trasformarlo in un albero bilanciato.
Esistono 4 tipi di rotazioni:
1. Rotazione a sinistra: se l'aggiunta di un nodo a destra dell'albero lo rende squilibrato, in tal caso, è necessario eseguire la rotazione a sinistra.
2. Rotazione a destra: se l'aggiunta di un nodo a sinistra dell'albero provoca uno squilibrio del nodo, è necessario eseguire la rotazione a destra. In altre parole, quando il numero di nodi aumenta sul lato sinistro, allora emerge la necessità di spostare gli elementi sul lato destro per bilanciarlo, quindi si dice che sia la rotazione a destra.
3. Rotazione sinistra-destra: questo tipo di rotazione è una combinazione delle 2 rotazioni sopra descritte. Questo tipo di rotazione si verifica quando un elemento viene aggiunto alla sottostruttura destra di un albero sinistro.
In tal caso, eseguire prima la rotazione a sinistra sulla sottostruttura seguita da una rotazione a destra dell'albero a sinistra.
4. Rotazione destra-sinistra: questo tipo di rotazione è anche composto da una sequenza di 2 rotazioni superiori. Questo tipo di rotazione è necessario quando un elemento viene aggiunto a sinistra della sottostruttura destra e l'albero diventa sbilanciato. In tal caso, eseguiamo prima la rotazione destra sulla sottostruttura destra e poi la rotazione sinistra sull'albero destro.
Operazioni sull'albero AVL in DS
Di seguito 3 operazioni che possono essere eseguite sull'albero AVL: -
1. Cerca
Questa operazione è simile all'esecuzione di una ricerca nella struttura di ricerca binaria. I passaggi seguiti sono i seguenti:
- Leggi l'elemento fornito dall'utente dire x.
- Confronta l'elemento dalla radice, se è lo stesso, quindi esci altrimenti vai al passaggio successivo.
- Se x
Altrimenti vai al bambino giusto e confronta di nuovo.
Seguire i processi B e C fino a trovare l'elemento e uscire.
Questo processo ha complessità O (log n).
Esempio:
 | Considera questo albero, dove dobbiamo eseguire una ricerca per il valore del nodo 9. Innanzitutto, lascia x = 9, valore radice (12)> x, quindi il valore deve trovarsi nella sottostruttura sinistra dell'elemento radice. |
 | Ora x viene confrontato con il valore del nodo 3 x> 3 quindi dobbiamo procedere verso la sottostruttura giusta. |
 | Ora x viene confrontato con il nodo (9), dove 9 == 9 restituisce true. Pertanto, la ricerca degli elementi viene completata nella struttura. |
2. Inserimento
Durante l'inserimento di un elemento nell'albero AVL, dobbiamo trovare l'elemento particolare della posizione che deve essere inserito e quindi l'elemento viene collegato come un inserimento in BST, ma successivamente viene verificato se l'albero è ancora bilanciato o meno cioè il fattore di equilibrio di un nodo è <= 1. E particolari rotazioni vengono eseguite come richiesto.
La complessità è O (log n).
Esempio: considera l'albero sottostante,
 | Ogni nodo ha un fattore di bilanciamento come 0, -1 o 1, quindi l'albero è bilanciato. Ora consente cosa succede quando viene inserito un nodo con valore 1. Il primo albero viene attraversato per trovare la posizione in cui deve essere inserito … 1 <2 viene quindi scritto come un figlio sinistro del nodo (2). |
 | Dopo l'inserimento, il nodo (9) diventa sbilanciato con un fattore di equilibrio = 2. Ora viene sottoposto a rotazione a destra. |
 | Un albero diventa in equilibrio dopo la rotazione a destra e quindi l'operazione di inserimento è stata completata con successo. |
3. Cancellazione
L'eliminazione di un elemento nell'albero AVL comprende anche la ricerca di un elemento nell'albero e la sua eliminazione. L'operazione di ricerca è la stessa di BST, e dopo aver trovato l'elemento da eliminare l'elemento viene rimosso dall'albero e gli elementi vengono regolati per renderlo nuovamente BST. Dopo che questi elementi sono stati controllati per avere un fattore di bilanciamento di 0, -1 o 1 e quindi vengono eseguite rotazioni adatte per renderlo bilanciato.
Complessità se O (log n).
 | Considera l'albero dato, i cui tutti hanno un fattore di equilibrio di 0, -1 o 1. Ora eliminiamo un nodo con valore 16. Il primo albero viene attraversato per trovare il nodo con valore 16 uguale a un algoritmo di ricerca. |
 | Il nodo 16 verrà sostituito con il predecessore inorder di questo nodo che è l'elemento più grande della sottostruttura sinistra, ovvero 12 L'albero è diventato sbilanciato, quindi è necessario eseguire la rotazione LL. |
 | Ora ogni nodo è diventato bilanciato. |
Conclusione - Albero AVL nella struttura dei dati
L'albero AVL è un discendente dell'albero della ricerca binaria ma supera il suo svantaggio di complessità crescente nel caso in cui gli elementi vengano ordinati. Monitora il fattore di bilanciamento dell'albero in modo che sia 0 o 1 o -1. Nel caso in cui l'albero diventi sbilanciato, vengono eseguite tecniche di rotazione corrispondenti per bilanciare l'albero.
Articoli consigliati
Questa è una guida all'albero AVL nella struttura dei dati. Qui discutiamo l'introduzione, le operazioni sull'albero AVL in DS e i tipi di rotazioni. Puoi anche consultare i nostri altri articoli correlati per saperne di più–
- jQuery Elements
- Che cos'è la scienza dei dati
- Tipi di alberi nella struttura dei dati
- Tipi di dati C #