Fino ad ora abbiamo visto strutture dati in cui le informazioni si mettono in fila indiana, come vagoni di un treno o persone in coda alla cassa (Array, Liste, Stack, Queue).
Tuttavia, se ci guardiamo attorno nel mondo reale, la maggior parte delle cose non è affatto disposta in fila indiana:
- Le cartelle e i documenti dentro il computer sono organizzati in una gerarchia di sottocartelle annidate.
- Le strade e le autostrade su Google Maps formano una gigantesca ragnatela con incroci, sensi unici e pedaggi.
- Sui social network come Instagram o Facebook, miliardi di utenti sono collegati tra loro da legami di amicizia o follower.
- Le pagine web di internet sono collegate tra loro tramite miliardi di link ipertestuali aperti.
Per gestire questa complessità, l’informatica utilizza le Strutture Dati Non Lineari: i maestosi Alberi (Trees) e gli universali Grafi (Graphs).
In questa guida scopriremo come funzionano gli Alberi Binari di Ricerca, come gli algoritmi esplorano queste reti e sveleremo il segreto dell’Algoritmo di Dijkstra, il motore matematico che permette al navigatore satellitare del nostro smartphone di trovare la strada più veloce per tornare a casa!
1. Gli Alberi: La Gerarchia Capovolta del Computer
Nel mondo della natura, gli alberi hanno le radici piantate per terra e i rami che crescono verso il cielo. In informatica, per una simpatica tradizione storica, gli alberi si disegnano sempre a testa in giù:
2. Gli Alberi Binari di Ricerca (BST): Trovare Tutto in 20 Passi
Tra tutti gli alberi, il più celebre è l’Albero Binario di Ricerca (BST – Binary Search Tree).
Si chiama "binario" perché ogni genitore può avere al massimo due figli: uno a Sinistra e uno a Destra.
La regola con cui vengono inseriti i numeri è semplicissima:
- Tutto ciò che è PIÙ PICCOLO del genitore va a SINISTRA.
- Tutto ciò che è PIÙ GRANDE del genitore va a DESTRA.
[ 50 ] <-- Radice
/ \
[ 20 ] [ 80 ]
/ \ / \
[ 10 ] [ 30 ][ 70 ] [ 90 ]
Perché è una struttura prodigiosa per le ricerche?
Immaginiamo di cercare il numero 70:
- Parti dalla radice (50). 70 è più grande di 50? Sì, quindi scendi a Destra (scartando all’istante l’intera metà sinistra dell’albero!).
- Arrivi a 80. 70 è più piccolo di 80? Sì, quindi scendi a Sinistra.
- Sei arrivato su 70! Trovato in appena 2 passaggi!
Con un albero binario ben bilanciato, anche se hai un archivio con 1.000.000 di dati, puoi trovare qualsiasi informazione compiendo al massimo circa 20 confronti (complessità logaritmica )!
3. I Grafi: La Mappa del Mondo Reale
Mentre gli alberi impongono una rigida gerarchia dall’alto verso il basso senza anelli, i Grafi non hanno regole gerarchiche: possono rappresentare qualsiasi tipo di rete aperta e interconnessa.
Un grafo è composto da due soli elementi:
- I Vertici (o Nodi): I punti della rete (ad esempio le città: Roma, Milano, Napoli, Firenze).
- Gli Archi (o Collegamenti): Le linee che uniscono i vertici (le autostrade o le tratte aeree che collegano le città).
4. Come Esplorare un Grafo: Visita in Ampiezza (BFS) vs Profondità (DFS)
Quando un algoritmo deve esplorare una rete (ad esempio per cercare se esiste un percorso o suggerirti amici in comune sui social), può scegliere tra due strategie:
1. BFS (Breadth-First Search – Visita in Ampiezza): I Sassi nello Stagno
L’algoritmo parte da un nodo ed esplora tutti i vicini immediati a distanza 1, poi tutti quelli a distanza 2, poi quelli a distanza 3, allargandosi a cerchi concentrici proprio come le onde generate da un sasso gettato in uno stagno d’acqua (utilizza una struttura a Coda FIFO).
- A cosa serve: È l’algoritmo perfetto per trovare il percorso con il minor numero di passaggi, o per trovare gli amici di primo grado e gli amici di secondo grado su Facebook!
2. DFS (Depth-First Search – Visita in Profondità): Il Labirinto
L’algoritmo si comporta come un esploratore intrappolato in un labirinto: sceglie un sentiero e corre dritto fino in fondo finché non incontra un muro o un vicolo cieco; a quel punto torna indietro di un passo (backtracking) e prova il sentiero a fianco (utilizza una struttura a Pila o la ricorsione).
- A cosa serve: Ottimo per risolvere labirinti, sudoku, scacchi o verificare se una rete è completamente connessa.
5. L’Algoritmo di Dijkstra: Come Google Maps Trova la Strada Migliore
Nel 1956, durante una pausa caffè mentre passeggiava con la fidanzata ad Amsterdam, il geniale informatico olandese Edsger Dijkstra progettò in appena venti minuti uno degli algoritmi più celebri e utilizzati della storia: l’Algoritmo di Dijkstra per i Cammini Minimi.
Come fa il navigatore a calcolare la rotta più veloce tra centinaia di migliaia di incroci stradali?
6. Quadro sinottico comparativo: Alberi contro Grafi
| Caratteristica | Struttura ad Albero (Tree) | Struttura a Grafo (Graph) |
|---|---|---|
| Gerarchia | Rigorosa (c’è sempre una Radice in alto e Figli sotto). | Assente: qualsiasi nodo può collegarsi a qualsiasi altro nodo. |
| Cicli e Anelli Chiusi | Severamente vietati: non puoi tornare indietro in tondo. | Consentiti: puoi avere anelli chiusi e percorsi circolari. |
| Punto d’Ingresso | Sempre unico e obbligato: la Radice (Root). | Arbitrario: puoi iniziare l’esplorazione da qualsiasi vertice. |
| Esempi nel Quotidiano | L’albero genealogico, il File System (cartelle/file), l’albero DOM delle pagine web. | Le reti stradali (Google Maps), le reti di amici sui social, la rete internet dei router. |
| Algoritmi Tipici | Ricerca binaria (), bilanciamento AVL, visita In-Order. | Algoritmo di Dijkstra, visita BFS (ampiezza), visita DFS (profondità), PageRank. |
7. Domande Frequenti su Alberi e Grafi (FAQ)
Che differenza c’è tra un Albero e un Grafo?
Un albero è in realtà un caso speciale e semplificato di grafo! Matematicamente parlando, un albero è semplicemente un grafo connesso e privo di cicli.
Perché gli Alberi di Ricerca devono essere "Bilanciati" (Alberi AVL o Red-Black)?
Se inserisci in un albero binario numeri già ordinati (es. 10, poi 20, poi 30, poi 40), tutti i numeri andranno a destra. L’albero diventerà una lunga linea dritta sbilanciata, comportandosi male come una lenta lista collegata ()! Gli algoritmi di bilanciamento (come gli alberi AVL o Red-Black) eseguono microscopiche "rotazioni" automatiche dei rami per mantenere la chioma folta e bassa, garantendo sempre la velocità massima .
Come fa Facebook a suggerirti "Persone che potresti conoscere"?
Usa la teoria dei grafi e l’algoritmo di visita in ampiezza (BFS): analizza il nodo del tuo profilo, guarda gli amici dei tuoi amici (nodi a distanza 2) e conta quante connessioni comuni avete. Più connessioni condivise ci sono tra due nodi, più è probabile che vi conosciate nella vita reale!
Che cos’è l’Albero DOM del browser web?
Quando il browser scarica una pagina web HTML, trasforma il codice in un albero chiamato DOM (Document Object Model): la radice è il tag <html>, da cui partono i due rami <head> e <body>, da cui si diramano i paragrafi <p>, le immagini <img> e i pulsanti <button>. Grazie a questa struttura ad albero, il codice JavaScript può trovare e modificare al volo qualsiasi elemento della pagina in una frazione di secondo!
8. Glossario essenziale
- Vertice (Vertex / Node): L’elemento fondamentale o incrocio di un grafo o di un albero contenente le informazioni.
- Arco (Edge): Il collegamento o segmento che unisce due vertici tra loro.
- Grafo Pesato: Un grafo in cui a ogni arco è associato un valore numerico indicante costo, distanza o tempo di percorrenza.
- Cammino Minimo: Il percorso tra due nodi la cui somma dei pesi degli archi attraversati è la minima possibile.
- Backtracking: La tecnica algoritmica che consiste nel tornare indietro sui propri passi quando si incontra un vicolo cieco per esplorare percorsi alternativi.
Fonti e Riferimenti Accademici Ufficiali
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C.: Introduction to Algorithms (4th Edition), MIT Press. Capitolo 12: "Binary Search Trees", Capitolo 22: "Elementary Graph Algorithms", Capitolo 24: "Single-Source Shortest Paths (Dijkstra’s Algorithm)".
- Dijkstra, Edsger W. (1959): A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, Vol. 1. La pubblicazione scientifica originale in cui Dijkstra formalizzò il calcolo del cammino minimo.
- Sedgewick, Robert, & Wayne, Kevin: Algorithms (4th Edition), Addison-Wesley. Capitolo 3: "Searching – Balanced Search Trees", Capitolo 4: "Graphs – Undirected, Directed, and Shortest Paths".