4 Spiegazione dei tipi di alberi nella struttura dei dati: proprietà e applicazioni

Che cos'è un albero nella struttura dei dati?

Un albero è un tipo di struttura dati che rappresenta dati gerarchici. Ha una struttura non lineare costituita da nodi collegati da spigoli. Tra gli altri tipi di strutture dati che eseguono operazioni in una struttura dati lineare, la complessità aumenta con l'aumento delle dimensioni dei dati. Tuttavia, la struttura dei dati ad albero fornisce un accesso più rapido ai dati che non sono lineari. Grazie alla disponibilità dei vari tipi di strutture dati e degli algoritmi ad esse associati, l'esecuzione dei compiti è diventata un modo semplice ed efficiente.

Alcune terminologie associate agli alberi nella struttura dei dati sono:

• Nodo : il nodo è un'entità in una struttura dati ad albero che contiene una chiave o un valore e puntatori ai suoi nodi figli.
• Nodo figlio : un nodo figlio è il discendente di qualsiasi nodo.
• Nodi foglia: i nodi che non hanno nodi figlio e sono il nodo più in basso in un albero. Sono anche chiamati nodi esterni.
• Radice : è il punto più alto di un albero.
• Nodo interno : il nodo che ha almeno un nodo figlio.
• Bordo: un bordo si riferisce alla connessione tra due nodi qualsiasi in un albero.
• Altezza di un nodo: numero di spigoli dal nodo alla foglia più profonda.
• Profondità di un nodo : numero di spigoli dalla radice al nodo.
• Altezza di un albero : Altezza del nodo radice.
• Grado di un nodo : numero totale di rami a quel nodo.
• Foresta: una collezione di alberi disgiunti.

Tipi di albero

1. Albero binario

L' albero binario è un tipo di struttura dati ad albero in cui ogni nodo padre ha un massimo di due nodi figlio. Come suggerisce il nome, binario significa due, quindi ogni nodo può avere 0, 1 o 2 nodi. Nella Figura 1 è mostrata una struttura di dati ad albero binario . Il nodo 1 nell'albero contiene due puntatori, uno per ogni nodo figlio. Il nodo 2 ha di nuovo due puntatori ciascuno per i due nodi figlio. Considerando che i nodi 3, 5 e 6 sono nodi foglia e quindi hanno puntatori nulli su entrambe le parti sinistra e destra.

Figura 1: una rappresentazione di un albero binario ( https://www.javatpoint.com/binary-tree ).

Proprietà di un albero binario

• Il numero massimo di nodi ad ogni livello di I è 2 i .
• L'altezza dell'albero nella Figura 1 è 3, il che significa che il numero massimo di nodi sarà (1+2+4+8) =15.

• All'altezza h, il numero massimo di nodi possibile è (20 + 21 + 22+….2h) = 2h+1 -1.

• All'altezza h, il numero minimo di nodi possibile è pari a h+1.

• Un numero minimo di nodi rappresenterà un albero con altezza massima e viceversa.

Anche gli alberi binari possono essere suddivisi nei seguenti tipi di albero:

• Albero binario completo: è un tipo speciale di albero binario. In questa struttura dati ad albero, ogni nodo padre o un nodo interno ha due figli o nessun nodo figlio.
• Albero binario perfetto: in questo tipo di struttura dati ad albero , ogni nodo interno ha esattamente due nodi figlio e tutti i nodi foglia sono allo stesso livello.
• Albero binario completo: assomiglia a quello dell'albero binario completo con alcune differenze.
• Ogni livello è completamente riempito.
• I nodi foglia si inclinano verso la sinistra dell'albero.
• Non è un requisito che l'ultimo nodo foglia abbia il fratello giusto, cioè un albero binario completo non deve essere un albero binario completo.
• Albero degenerato o patologico: questi alberi hanno un solo figlio a sinistra oa destra del nodo padre.
• Albero binario inclinato: è un albero patologico o degenerato in cui l'albero è dominato dai nodi sinistro o destro. Pertanto, ci sono due tipi di alberi binari inclinati, cioè l'albero binario inclinato a sinistra o l'albero binario inclinato a destra.
• Albero binario bilanciato: la differenza tra l'altezza del sottoalbero sinistro e destro per ciascun nodo è 0 o 1.

2. Albero di ricerca binaria

Queste strutture ad albero non sono lineari e un nodo è connesso a un numero di nodi. Il nodo può essere connesso a un massimo di due nodi figlio. Si chiama albero di ricerca binario perché:

• Ogni nodo ha un massimo di due nodi figlio.
• Può essere utilizzato per cercare un elemento in 0(log(n)) tempo e quindi noto come albero di ricerca.

Figura: un esempio di albero di ricerca binario ( https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm )

Le proprietà di un albero di ricerca binario sono:

• Il valore in tutti i nodi di un sottoalbero sinistro deve essere inferiore al valore nel nodo radice.
• Il valore in tutti i nodi di un sottoalbero destro deve essere maggiore del valore nel nodo radice.

3. Albero AVL

Gli alberi AVL sono i tipi o le varianti di un albero binario. Consiste di proprietà sia del binario che di un albero di ricerca binario. Inventati da Adelson Velsky Lindas, questi alberi sono autobilanciati, il che significa che l'altezza del sottoalbero sinistro e del sottoalbero destro è bilanciata. Questo equilibrio è misurato in termini di un fattore di bilanciamento.

Fattore di bilanciamento:

• È la differenza tra il sottoalbero di sinistra e il sottoalbero di destra.
• Il valore di un fattore di bilanciamento deve essere 0, -1 o 1. Pertanto, ogni nodo di un albero AVL dovrebbe essere costituito da un valore del fattore di bilanciamento, ovvero 0, -1 o 1.
• Fattore di bilanciamento = (Altezza del sottoalbero sinistro – Altezza del sottoalbero destro)
• Si dice che un albero AVL sia un albero bilanciato se il fattore di equilibrio di ciascun nodo è compreso tra -1 e 1.

I valori dei nodi diversi da -1, a 1 in un albero AVL rappresenteranno un albero sbilanciato che deve essere bilanciato.

• Se un nodo ha un fattore di bilanciamento di 1, significa che il sottoalbero di sinistra è un livello più alto del sottoalbero di destra.
• Se un nodo ha un fattore di equilibrio pari a 0, significa che l'altezza del sottoalbero sinistro e del sottoalbero destro è uguale.
• Se un nodo ha un fattore di bilanciamento di -1, significa che il sottoalbero di destra è un livello più alto del sottoalbero di sinistra o il sottoalbero di sinistra è un livello più basso del sottoalbero di destra.

4. Albero B

B Tree è una forma più generalizzata di un albero di ricerca binario. È anche conosciuto come l'albero della via m equilibrato in altezza, dove m è l'ordine dell'albero. Ogni nodo dell'albero può avere più di una chiave e più di due nodi figlio. Nel caso di un albero binario, i nodi foglia potrebbero non essere allo stesso livello. Tuttavia, nel caso di un B Tree, tutti i nodi foglia dovrebbero essere allo stesso livello.

Proprietà di un albero B:

• Le chiavi sono memorizzate in ordine crescente per ogni nodo x.
• Un valore booleano "x.leaf" esiste in ogni nodo, che è vero se x è una foglia.
• I nodi interni dovrebbero avere al massimo "n-1" chiavi, dove n è l'ordine dell'albero. Dovrebbe anche avere un puntatore per ogni bambino.
• Tutti i nodi avranno al massimo n figli e almeno n/2 figli, eccetto il nodo radice.
• I nodi foglia dell'albero hanno la stessa profondità.
• Il nodo radice avrà un minimo di 1 chiave e almeno due figli.
• Se n ≥ 1, allora per ogni albero B di n chiavi di altezza h e grado minimo t ≥ 2, h ≥ logt (n+1)/2.

Applicazioni

• L'albero di ricerca binaria può essere applicato per cercare un elemento in un insieme di elementi.
• Gli alberi dell'heap vengono utilizzati per l'ordinamento dell'heap.
• I router moderni utilizzano un tipo di albero chiamato Tries per memorizzare le informazioni di routing.
• I B-Trees e i T-Trees sono utilizzati principalmente dai database più diffusi per archiviare i propri dati.
• Un albero della sintassi viene utilizzato dai compilatori per convalidare la sintassi di ogni programma scritto.

Conclusione

Le strutture dati forniscono un modo organizzato di archiviare i dati per una facile gestione e una gestione efficace. Esistono vari tipi di strutture dati per diversi tipi di dati. In base al tipo di dati che devono essere conservati, sono scelti dall'utente.

Gli alberi sono tipi di tali strutture di dati in cui è possibile archiviare il tipo gerarchico di dati. I dati vengono archiviati nei nodi che a volte memorizzano il riferimento per altri nodi chiamati nodi figli.

In base al numero di nodi figli, gli alberi possono essere classificati in vari tipi come indicato nell'articolo. In base alla disposizione dei nodi nei tipi di albero, ogni struttura ad albero ha proprietà associate. Con i diversi tipi di operazioni che possono essere eseguite dalle diverse classi di alberi, questo tipo di struttura dei dati ha trovato applicazioni negli algoritmi di ordinamento e nella memorizzazione dei dati.

Un programma Executive PG in Software Development - Specializzazione in Full Stack Development, a cura di upGrad e IIIT-Bangalore, può aiutarti a migliorare il tuo profilo e garantire migliori opportunità di lavoro come programmatore.