Esempi di Alberi¶
Gli alberi sono usati in molti ambiti dell’informatica, come nei sistemi operativi, sistemi grafici, database e reti.
Consideriamo alcuni esempi. Il primo è un albero di classificazione in ambito biologico. Figura 1 mostra un esempio di classificazione biologica degli animali. Possiamo osservare diverse proprietà degli alberi. La prima proprietà che questo esempio dimostra è che gli alberi sono gerarchici, ovvero che sono strutturati in livelli con le cose più generiche vicino alla radice, in cima, e le cose più specifiche in basso. La cima della gerarchia è il Regno, il livello successimo dell’albero (ovvero i “figli” del livello sopra) è il Phylum, poi c’è la Classe e così via. Tuttavia, non importa quanto in profondità andiamo nella classificazione, tutti gli organismi sono ancora animali.
Figura 1: Tassonomia di alcuni animali comuni
Notiamo che possiamo partire dalla cima dell’albero e seguire un cammino fatto di cerchi e frecce fino al basso. Ad ogni livello dell’albero, potremmo chiederci qualcosa e intraprendere un cammino di conseguenza. Per esempio, potremmo chiederci, “Questo animale fa parte dei cordati o degli artropodi?” Se la risposta è cordati (“Chordate” nella figura) allora seguiamo il cammino corrispondente e ci chiediamo “E’ un mammifero?” Altrimenti ci fermiamo (ma solo in questo esempio semplificato). Quando siamo al livello dei mammiferi, ci chiediamo “Si tratta di un primate o di un carnivoro?” Possiamo seguire i cammini seguenti fino a che arriviamo alla base dell’albero dove abbiamo il nome comune.
La seconda proprietà degli alberi è che tutti i figli di un nodo sono indipendenti dai figli di un altro nodo. Per esempio, il Genus Felis ha come figli Domestica e Leo. Il Genus Musca ha anche lui un figlio chiamato Domestica, ma si tratta di un nodo differente e indipendente dal figlio Domestica di Felis. Questo significa che possiamo cambiare il nodo che è figlio di Musca senza modificare il figlio di Felis.
Una terza proprietà è che ogni nodo foglia è unico. Possiamo specificare un cammino dalla radice dell’albero che identifica univocamente ogni specie di animali; per esempio, Animalia \(\rightarrow\) Chordate \(\rightarrow\) Mammal \(\rightarrow\) Carnivora \(\rightarrow\) Felidae \(\rightarrow\) Felis \(\rightarrow\) Domestica.
Un altro esempio di alberi che usiamo tutti i giorni è il file system. In un file system, le cartelle sono organizzate come un albero. Figura 2 mostra una piccola parte di un file system Unix.
Figura 2: Una piccola parte di un File System Linux
L’albero relativo a un file system ha molto in comune con l’albero di classificazione biologica che abbiamo visto. Possiamo seguire un cammino dalla radice a qualsiasi cartella. Il cammino identifica univocamente le sottocartelle e tutti i file che sono contenuti. Un’altra proprietà importante, derivata dalla sua natura gerarchica, è quella di poter muovere intere sezioni di un albero (chiamato subtree) in una diversa posizione dell’albero senza cambiare i livelli più bassi della gerarchia. Per esempio, possiamo prendere l’intero sottoalbero che comincia per /etc/, staccare etc/ dalla radice e riattaccarlo sotto usr/. Questo cambierebbe l’unico nome di cammino di httpd da /etc/httpd a /usr/etc/httpd, ma non cambia il contenuto o i figli della cartella httpd.
Un altro esempio di albero è una pagina web. La seguente è un esempio di una semplcie pagina web scritta in HTML. Figura 3 mostra l’albero che corrisponde a ogni tag dell’HTML usati per creare la pagina.
<html xmlns="http://www.w3.org/1999/xhtml"
xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type"
content="text/html; charset=utf-8" />
<title>simple</title>
</head>
<body>
<h1>A simple web page</h1>
<ul>
<li>List item one</li>
<li>List item two</li>
</ul>
<h2><a href="http://www.cs.luther.edu">Luther CS </a><h2>
</body>
</html>
Figura 3: Un albero corrispondente agli elementi di Markup di una pagina web
Il sorgente HTML e l’albero che accompagna il sorgente mostra un’altra gerarchia. Notiamo che ogni livello dell’albero corrisponde a un livello innestato all’interno dei tag HTML. Il primo tag nel sorgente è
<html> e l’ultimo è </html> Tutti i tag rimanenti nella pagina sono all’interno della coppia. Questa proprietà di innestamento vale in tutti i livelli dell’albero.