Alberi informatica, spiegati in dettaglio
Introduzione agli alberi in informatica
Gli alberi sono una delle strutture dati più fondamentali e versatili in informatica. Queste strutture dati giocano un ruolo cruciale nell’organizzazione, nell’accesso e nella manipolazione dei dati in molte applicazioni software.
In questo articolo, esploreremo tutto ciò che c’è da sapere sugli alberi in informatica e come siano essenziali per molte attività di elaborazione dati.
Questo articolo fa parte di una raccolta dedicata alla preparazione di un colloquio tecnico in informatica. Se vuoi saperne di più, clicca qui!
Supporta EasyScience acquistando il prodotto tramite il nostro link! Ricorda: consigliamo solo prodotti che riteniamo validi e testati.
Cos’è un albero in informatica?
Un albero in informatica è una struttura dati gerarchica composta da nodi collegati tra loro da archi. In un albero, c’è sempre un nodo speciale chiamato radice, da cui si diramano tutti gli altri nodi.
Un albero è un particolare tipo di grafo!
Gli altri nodi sono suddivisi in sottoalberi, che possono essere ulteriormente suddivisi in sottoalberi più piccoli. Questa gerarchia rende gli alberi ideali per rappresentare dati con una struttura annidata.
Se vogliamo vedere un albero dal punto di vista dei puntatori, possiamo immaginare ogni nodo formato da due puntatori: uno al sottoalbero destro e uno al sottoalbero sinistro (se presenti) che permettono la visita dei nodi figli fino alle foglie (vedi la figura in basso).
Le definizioni più importanti
- Nodo: ogni elemento in un albero è un nodo. I nodi contengono i dati e possono avere zero o più nodi figli, a seconda del tipo di albero;
- Arco: gli archi collegano i nodi tra loro e definiscono la relazione gerarchica tra di essi. Ogni arco ha una direzione, dal padre al figlio;
- Radice: il nodo iniziale di un albero è chiamato radice. Tutti gli altri nodi sono raggiungibili dalla radice seguendo gli archi;
- Foglia: i nodi che non hanno figli sono chiamati foglie. Sono gli estremi dell’albero.
Definizioni in dettaglio degli alberi in informatica
Un albero è una coppia \(T = (N, A)\) costituita da un insieme N di nodi e da un insieme \( A \subseteq N \times N \) di coppie di nodi, dette archi.
- In un albero, ogni nodo u (tranne la radice) ha zero o più figli v tali che \((u,v) \in A\).
- Un nodo u può avere zero o più figli v tali che \((u,v)\in A\) e il loro numero d viene chiamato grado del nodo.
Nodi foglia e interni
- Un nodo senza figli è chiamato foglia, mentre tutti i nodi che non sono né foglia né radice sono chiamati interni.
Profondità di un albero
La profondità (o livello) di un nodo è il numero di archi che passano dal nodo stesso alla radice. Può anche essere definita in questo modo:
- la radice ha profondità zero;
- se un nodo ha una profondità k, tutti i figli hanno profondità k + 1.
Altezza di un albero
- L’altezza di un albero è la massima profondità a cui si trova una foglia.
Supporta EasyScience acquistando il prodotto tramite il nostro link! Ricorda: consigliamo solo prodotti che riteniamo validi e testati.
Tipi comuni di alberi
Esistono numerosi tipi di alberi in informatica, ognuno con caratteristiche uniche e utilizzi specifici. Alcuni dei più comuni includono:
- Alberi binari: ogni nodo tranne le foglie ha al massimo d = 2 nodi figli. Sono utilizzati in molte applicazioni, come gli alberi di ricerca binaria;
- Alberi d-ari: tutti i nodi tranne le foglie hanno grado d. Ad esempio, gli alberi di decisione nei modelli di machine learning;
- Alberi completi: solo alberi d-ari in cui tutte le foglie sono sullo stesso livello;
- Alberi bilanciati: se la profondità di tutte le foglie è uguale all’altezza dell’albero o a questa meno 1;
- Alberi non bilanciati: alberi in cui la distribuzione dei nodi può essere sbilanciata.
Visite di alberi in informatica
Per effettuare ricerche negli alberi, esistono tre tipologie di algoritmi:
- Visita generica;
- Visita in profondità;
- Visita in profondità ricorsiva;
- Visita in ampiezza.
Visita generica
In questo metodo di visita di un albero, per effettuare le ricerche all’interno di un albero, bisogna seguire tutti i rami possibili a partire dalla radice.
Di seguito è riportato uno pseudo-codice dell’algoritmo di visita generica:
visitaGenerica(nodo r)
inserisci il nodo r all'interno dell'insieme S
while (s.length != 0) do
estrai un nodo u da S
visita il nodo u
inserisci a S l'unione tra S e i figli di uL’algoritmo inizia aggiungendo il nodo radice r all’insieme S che contiene tutti i nodi da visitare.
I nodi da visitare si dicono aperti, mentre quelli visitati si dicono chiusi.
Successivamente, fino a quando S non è vuoto, si estrae un nodo u da S, si visita e poi si inseriscono nell’insieme S tutti i nodi figli di u.
L’algoritmo di visita generica a partire dalla radice di un albero con n nodi, ha complessità computazionale O(n) (se non conosci l’argomento, visita il nostro articolo!).
Visita in profondità
L’algoritmo di visita in profondità (in inglese Depth-First Search o DFS) è un metodo per esplorare o attraversare una struttura dati ad albero in modo sistematico. L’obiettivo principale della visita in profondità è esplorare più in profondità possibile lungo un ramo dell’albero prima di tornare indietro e esplorare altri rami.
L’algoritmo DFS utilizza uno stack (se non sai cos’è visita il nostro articolo) o la ricorsione per tenere traccia dei nodi da visitare e da cui partire.
Ecco come funziona:
- Si inizia dalla radice dell’albero o dal nodo di partenza specificato;
- Il nodo viene visitato;
- Si sceglie un nodo del sotto-albero di sinistra non ancora visitato e ci si sposta su di esso;
- Si ripetono i passi 2 e 3 finché non si è visitato l’intero sottoalbero di sinistra;
- Si torna indietro al nodo precedente e si riprova a visitare i nodi del sottoalbero di destra non ancora esplorati. Questo è dove l’uso di uno stack o della ricorsione è cruciale. Se si usa uno stack, si rimuove il nodo corrente dallo stack e si torna indietro al nodo precedente. Se si sta usando la ricorsione, la chiamata di funzione corrente terminerà, riportando il flusso di esecuzione al chiamante precedente;
- Si ripetono i passi 2-5 finché non si sono visitati tutti i nodi desiderati nell’albero.
visitaDFS(nodo r)
Pila S
S.push(r)
while(not S.isEmpty()) do
si estrae un nodo dalla pila S (pop)
if (u != null) then
visita il nodo u
S.push(figlio dx di u)
S.push(figlio sx di u)Con la visita in profondità, l’albero mostrato sopra verrebbe visitato in questo modo:
1 – 2 – 3 – 4 – 5 – 6
Naturalmente, impilando prima il figlio sinistro poi quello destro si ottiene un algoritmo del tutto simmetrico a quello proposto.
Visita in profondità ricorsiva
L’algoritmo di visita in profondità è basato su una funzione ricorsiva che visita i nodi dell’albero in profondità prima di passare ai nodi fratelli.
Di seguito, è riportato uno pseudo-codice della visita in profondità ricorsiva:
algoritmo visitaDFSRicorsiva(nodo r)
if (r = null) then return
visita il nodo r
visitaDFSRicorsiva(figlio sx di r)
visitaDFSRicorsiva(figlio dx di r)Esistono tre varianti della visita in profondità ricorsiva:
- Visita in preordine;
- Visita simmetrica;
- Visita in postordine.
Visita in preordine
Questo approccio visita prima tutti i nodi del sottoalbero sinistro, poi il nodo corrente e infine il sottoalbero destro.
Prendendo il nostro solito albero mostrato sopra, la sequenza dei nodi visitati sarà:
1 – 2 – 3 – 4 – 5 – 6
Visita simmetrica
L’algoritmo di visita simmetrica, noto anche come “in-order traversal” in inglese, prende il suo nome dalla sequenza in cui visita i nodi dell’albero.
Ecco come funziona l’algoritmo:
- Inizia dalla radice dell’albero;
- Se il nodo corrente non è nullo, sposta il cursore o il puntatore al nodo più a sinistra;
- Continua a spostarti verso sinistra finché non raggiungi un nodo nullo;
- Dopo aver visitato il nodo più a sinistra, si visita il suo genitore (il nodo precedente nella sequenza);
- Se il genitore ha un figlio destro che non è stato visitato, sposta il cursore o il puntatore su quel figlio destro e ripeti il processo dal passo 2;
- Continua questo processo fino a quando si sono visitati tutti i nodi dell’albero.
Prendendo il nostro solito albero mostrato sopra, la sequenza dei nodi visitati sarà:
3 – 2 – 4 – 1 – 5 – 6
Visita in post-ordine
In questa tipologia di visita, si effettuano prima le chiamate ricorsive sul figlio sinistro e destro ed infine si visita la radice.
Prendendo il nostro solito albero mostrato sopra, la sequenza dei nodi visitati sarà:
3 – 4 – 2 – 6 – 5 – 1
Visita in ampiezza
Questo algoritmo prende il nome dalla sua caratteristica principale, che è quella di visitare prima tutti i nodi adiacenti al nodo radice e successivamente tutti i loro figli, e così via, fino a esplorare l’intero albero.
Questo processo è noto anche come “Breadth-First Search” (BFS) in inglese.
Prendendo il nostro solito albero mostrato sopra, la sequenza dei nodi visitati sarà:
1 – 2 – 5 – 3 – 4 – 6
Supporta EasyScience acquistando il prodotto tramite il nostro link! Ricorda: consigliamo solo prodotti che riteniamo validi e testati.
Utilità degli alberi in informatica
Gli alberi trovano impiego in numerose applicazioni informatiche, tra cui:
- Ricerca e ordinamento: gli alberi di ricerca binaria consentono di eseguire ricerche efficienti e ordinamenti rapidi;
- Gestione delle directory: i sistemi operativi utilizzano alberi per organizzare i file nel sistema;
- Strutture gerarchiche: gli alberi rappresentano gerarchie, come l’albero genealogico o la struttura di un sito web;
- Complessità computazionale: gli alberi sono utilizzati per analizzare la complessità dei problemi in algoritmi e teoria computazionale;
- Machine learning: gli alberi di decisione sono utilizzati in modelli di machine learning per prendere decisioni basate su input multidimensionali.
Bibliografia
- McDowell, Gayle Laakmann, 1982-. (2011). Cracking the coding interview : 150 programming questions and solutions. Palo Alto, CA :CareerCup, LLC
- C. Demetrescu, I. Finocchi, G. F. Italiano: Algoritmi e strutture dati, McGraw-Hill
In questa pagina sono presenti link di affiliazione che garantiscono a questo sito una piccola quota di ricavi, senza variazione del prezzo per l'acquirente.
