Prima di conoscere le differenze tra l'albero di ricerca binario e l'albero AVL, dovremmo conoscere separatamente l'albero di ricerca binario e l'albero AVL.
Cos'è un albero di ricerca binario?
IL albero di ricerca binario è un albero albero binario. Come sappiamo, quell'albero può avere un numero di figli, mentre; l'albero binario può contenere al massimo due figli. Quindi, il vincolo di un albero binario è seguito anche dall'albero binario di ricerca. Ogni nodo in un albero di ricerca binario dovrebbe avere al massimo due figli; in altre parole possiamo dire che l'albero binario di ricerca è una variante dell'albero binario.
Anche l'albero di ricerca binaria segue le proprietà della ricerca binaria. Nella ricerca binaria, tutti gli elementi di un array devono essere ordinati. Calcoliamo l'elemento centrale nella ricerca binaria in cui la parte sinistra dell'elemento centrale contiene il valore inferiore al valore medio e la parte destra dell'elemento centrale contiene i valori maggiori del valore medio.
Nell'albero di ricerca binario, l'elemento centrale diventa il nodo radice, la parte destra diventa il sottoalbero destro e la parte sinistra diventa il sottoalbero sinistro. Pertanto possiamo dire che l'albero binario di ricerca è una combinazione di a albero binario E ricerca binaria .
Nota: l'albero di ricerca binario può essere definito come l'albero binario in cui tutti gli elementi del sottoalbero sinistro sono minori del nodo radice e tutti gli elementi del sottoalbero destro sono maggiori del nodo radice.
Complessità temporale nell'albero di ricerca binario
Se l'albero binario di ricerca è quasi un albero bilanciato allora tutte le operazioni avranno una complessità temporale di O(log) perché la ricerca è divisa nel sottoalbero sinistro o destro.
quali sono le dimensioni dello schermo del mio computer
Se l'albero di ricerca binario è inclinato a sinistra o a destra, tutte le operazioni avranno la complessità temporale di SU) perché dobbiamo attraversare fino agli n elementi.
Cos'è l'albero AVL?
UN Albero AVL è un albero di ricerca binario autobilanciante in cui la differenza tra le altezze dei sottoalberi sinistro e destro non può essere maggiore di uno. Questa differenza è nota come fattore di equilibrio. Nell'albero AVL, i valori del fattore di equilibrio potrebbero essere -1, 0 o 1.
Come avviene l'autobilanciamento dell'albero binario di ricerca?
Come sappiamo, l'albero AVL è un albero di ricerca binario autobilanciante. Se l'albero di ricerca binario non è bilanciato, può essere autobilanciato con alcune riorganizzazioni. Queste riorganizzazioni possono essere eseguite utilizzando alcune rotazioni.
Comprendiamo l'autobilanciamento attraverso un esempio.
Supponiamo di voler inserire 10, 20, 30 in un albero AVL.
Di seguito sono riportati i modi per inserire 10, 20, 30 in un albero AVL:
Passo 1: Per prima cosa creiamo un albero di ricerca binario, come mostrato di seguito:
Passo 2: Nella figura sopra, possiamo osservare che l'albero è sbilanciato perché il fattore di equilibrio del nodo 30 è 2. Per renderlo un albero AVL, dobbiamo eseguire alcune rotazioni. Se eseguiamo la rotazione verso destra sul nodo 20 allora il nodo 30 si sposterà verso il basso, mentre il nodo 20 si sposterà verso l'alto, come mostrato di seguito:
Come possiamo osservare, l'albero finale segue la proprietà dell'albero di Ricerca Binaria e di un albero bilanciato; quindi, è un albero AVL.
conversione del tipo e casting in Java
Nel caso, l'albero lo era albero sbilanciato, quindi eseguiamo la giusta rotazione sul nodo.
Passo 1: Per prima cosa creiamo un albero di ricerca binario come mostrato di seguito:
Passo 2: Nella figura sopra, possiamo osservare che l'albero è sbilanciato perché il fattore di equilibrio del nodo 10 è -2. Per renderlo un albero AVL, dobbiamo eseguire alcune rotazioni. È un albero sbilanciato a destra, quindi eseguiremo la rotazione a sinistra. Se eseguiamo la rotazione a sinistra sul nodo 20, il nodo 20 si sposterà verso l'alto e il nodo 10 si sposterà verso il basso, come mostrato di seguito:
Come possiamo osservare, l'albero finale segue la proprietà del Albero di ricerca binaria e un albero equilibrato ; pertanto, è un albero AVL.
Passo 1: Per prima cosa creiamo l'albero di ricerca binaria come mostrato di seguito:
Passo 2: Nella figura sopra, possiamo osservare che l'albero è sbilanciato perché il fattore di equilibrio del nodo radice è 2. Per renderlo un albero AVL, dobbiamo eseguire alcune rotazioni. Lo scenario precedente è sbilanciato da sinistra a destra poiché un nodo è a sinistra del suo nodo genitore e un altro è a destra del suo nodo genitore. Innanzitutto, eseguiremo la rotazione a sinistra e la rotazione avverrà tra i nodi 10 e 20. Dopo la rotazione a sinistra, 20 si sposterà verso l'alto e 10 si sposterà verso il basso come mostrato di seguito:
cos'è desktop.ini
Tuttavia, l'albero è sbilanciato, quindi eseguiamo la giusta rotazione sull'albero. Una volta eseguita la giusta rotazione sull'albero, l'albero si presenterà come mostrato di seguito:
Come possiamo osservare nell'albero sopra, l'albero segue la proprietà dell'albero di ricerca binaria e di un albero bilanciato; pertanto, è un albero AVL.
Passo 1: Per prima cosa creiamo l'albero di ricerca binaria, come mostrato di seguito:
Passo 2: Nella figura sopra, possiamo osservare che l'albero è sbilanciato perché il fattore di equilibrio del nodo radice è 2. Per renderlo un albero AVL, dobbiamo eseguire alcune rotazioni. Lo scenario precedente è sbilanciato da destra a sinistra poiché un nodo è a destra del suo nodo genitore e un altro nodo è a sinistra del suo nodo genitore. Innanzitutto, eseguiremo la rotazione a destra che avviene tra i nodi 30 e 20. Dopo la rotazione a destra, 20 si sposterà verso l'alto e 30 si sposterà verso il basso come mostrato di seguito:
Tuttavia, l'albero sopra è sbilanciato, quindi dobbiamo eseguire la rotazione a sinistra sul nodo. Una volta eseguita la rotazione a sinistra, il nodo 20 si sposterà verso l'alto e il nodo 10 si sposterà verso il basso come mostrato di seguito:
Come possiamo osservare nell'albero sopra, l'albero segue la proprietà dell'albero di ricerca binaria e di un albero bilanciato; quindi, è un albero AVL.
Differenze tra l'albero di ricerca binaria e l'albero AVL
| Albero di ricerca binaria | Albero AVL |
|---|---|
| Ogni albero binario di ricerca è un albero binario perché entrambi gli alberi contengono al massimo due figli. | Ogni albero AVL è anche un albero binario perché anche l'albero AVL ha due figli massimi. |
| Nella BST non esiste alcun termine, come fattore di equilibrio. | Nell'albero AVL, ciascun nodo contiene un fattore di equilibrio e il valore del fattore di equilibrio deve essere -1, 0 o 1. |
| Ogni albero di ricerca binaria non è un albero AVL perché BST potrebbe essere un albero bilanciato o sbilanciato. | Ogni albero AVL è un albero di ricerca binario perché l'albero AVL segue la proprietà del BST. |
| Ogni nodo nell'albero di ricerca binaria è costituito da tre campi, ovvero il sottoalbero sinistro, il valore del nodo e il sottoalbero destro. | Ogni nodo nell'albero AVL è costituito da quattro campi, ovvero sottoalbero sinistro, valore del nodo, sottoalbero destro e fattore di equilibrio. |
| Nel caso dell'albero di ricerca binaria, se vogliamo inserire un nodo qualsiasi nell'albero allora confrontiamo il valore del nodo con il valore della radice; se il valore di nodo è maggiore del valore del nodo radice allora il nodo viene inserito nel sottoalbero di destra altrimenti il nodo viene inserito nel sottoalbero di sinistra. Una volta inserito il nodo non è necessario verificare il fattore di equilibrio dell'altezza affinché l'inserimento venga completato. | Nel caso dell'albero AVL, per prima cosa troveremo il luogo adatto in cui inserire il nodo. Una volta inserito il nodo, calcoleremo il fattore di equilibrio di ciascun nodo. Se il fattore di equilibrio di ciascun nodo è soddisfatto l'inserimento è completato. Se il fattore di equilibrio è maggiore di 1, allora dobbiamo eseguire alcune rotazioni per bilanciare l'albero. |
| Nell'albero di ricerca binaria, l'altezza o profondità dell'albero è O(n) dove n è il numero di nodi nell'albero di ricerca binaria. | Nell'albero AVL, l'altezza o profondità dell'albero è O(logn). |
| È semplice da implementare poiché dobbiamo seguire le proprietà di ricerca binaria per inserire il nodo. | È complesso da implementare perché nell'albero AVL dobbiamo prima costruire l'albero AVL e poi controllare il bilanciamento dell'altezza. Se l'altezza è sbilanciata allora dobbiamo eseguire alcune rotazioni per bilanciare l'albero. |
| Il BST non è un albero equilibrato perché non segue il concetto del fattore di equilibrio. | L'albero AVL è un albero equilibrato in altezza perché segue il concetto del fattore di equilibrio. |
| La ricerca è inefficiente in BST quando c'è un gran numero di nodi disponibili nell'albero perché l'altezza non è bilanciata. | La ricerca è efficiente nell'albero AVL anche quando è presente un numero elevato di nodi nell'albero poiché l'altezza è bilanciata. |