Gli alberi

Organizzazioni di dati:

Lineari: ogni elemento ha un solo predecessore e un solo successore.
Non lineare o gerarchico: ad esempio gli alberi. Un albero si compone di due componenti: il nodo (che contiene le informazioni) e l'arco (che collega gerarchicamente coppie di nodi). Un nodo in un albero possiede un solo predecessore, ma può avere molti successori.

Come in botanica, un albero ha una radice, un tronco che si può dividere in due o più rami, che a loro volta possono ridividersi. Si rappresenta tuttavia con la radice in alto (come un albero genealogico). Nell'esempio vediamo un albero i cui nodi contengono valori interi (la radice contiene il valore 10).

Un albero può essere vuoto (se non ha nessun nodo), oppure ha un nodo radice che ha una sequenza di zero o più nodi figli, i quali sono a loro volta radici di altrettanti sotto-alberi .

Gli alberi si prestano per rappresentare organizzazioni gerarchiche di informazioni, ad esempio: file system.

Alberi: terminologia

Per chiamare i nodi di un albero e le relazioni tra di essi si usano termini botanici e genealogici o di parentela.
Il predecessore di un nodo è detto padre, mentre i successori sono detti figli.

La relazione antenato-discendente generalizza quella di padre-figlio nel modo intuitivo. Un nodo che non ha predecessori è detto radice ed è l'unico per l'albero.
Un nodo senza successori è detto foglia.
Si parla di profondità (ovvero l'altezza dell'albero) e ampiezza (ovvero la larghezza).

Gli alberi binari

Un albero binario è un albero in cui ogni nodo ha al massimo due figli. Se il sottoalbero sinistro (risp. destro) di un albero non è vuoto, la sua radice viene detta figlio sinistro (risp. destro) della radice dell'intero albero (che è il padre).

Ad esempio, nell'albero seguente [il nodo contenente] 10 è la radice dell'albero, ed ha sia un figlio sinistro (20) che un figlio destro (2). I nodi 1, 29 e 7 sono foglie. Il nodo 20 è il padre di 3 e un antenato di 29, che è un discendente di 10. Il nodo 3 ha soltanto il figlio sinistro, perché il suo sottoalbero destro è vuoto.

Gli alberi binari hanno una elegante definizione ricorsiva:

Un albero binario è una struttura definita su un insieme di nodi che:

non contiene nessun nodo (albero vuoto), oppure
contiene un nodo radice, un albero binario detto sottoalbero sinistro ed un albero binario detto sottoalbero destro.

Molti algoritmi su alberi binari possono essere descritti in modo naturale sfruttando questa definizione ricorsiva, comprendendo un caso base (per l'albero vuoto) e una clausola ricorsiva (con due chiamate ricorsive, per i due sottoalberi).

Visita di un albero binario

"Visitare" un albero significa esaminare sequenzialmente tutti i suoi nodi. Ci sono tre tipi principali di visite:

Nella visita in ordine simmetrico si visita il sottoalbero sinistro, quindi si esamina la radice e infine si visita il sottoalbero destro.
Nella visita in ordine anticipato si esamina prima la radice e quindi si visitano il sottoalbero sinistro e quello destro.
Nella visita in ordine posticipato si visitano prima il sottoalbero sinistro poi quello destro e infine si esamina la radice.

Altri tre tipi di visite si ottengono dai precedenti scambiando "sinistro" con "destro".

Ricerca in un albero binario: usando una visita in ordine qualsiasi, si può stabilire se un certo oggetto appartiene o meno ad un dato albero binario. Si noti che:

il caso base è banale (come sempre): se l'albero è vuoto, si restituisce false;
la visita viene interrotta non appena si trova l'oggetto cercato.

Alberi binari di ricerca

Un albero binario di ricerca (ABR) è un albero binario tale che:

sui valori delle chiavi dei suoi nodi è definito un ordinamento totale;
soddisfa la seguente proprietà:

Per ogni nodo n dell'albero:

tutte le chiavi dei nodi contenuti nel sottoalbero sinistro di n hanno valore strettamente minore della chiave contenuta in n,

tutte le chiavi dei nodi contenuti nel sottoalbero destro di n hanno valore strettamente maggiore della chiave contenuta in n.

Un esempio, in cui le chiavi sono interi con l'ovvio ordinamento...

Si noti che in un ABR non ci possono essere due nodi con la stessa chiave.

Un'importante proprietà di un ABR è la seguente:

La visita in ordine simmetrico di un albero binario di ricerca genera una sequenza crescente di tutte le sue chiavi.

Ricerca in un ABR

Per la ricerca di un elemento in un albero binario di ricerca vediamo il primo esempio di algoritmo che sfrutta la proprietà (ABR). Come nel caso della ricerca binaria su un array, ogni indagine nell'ABR permette di eliminare metà degli elementi su cui continuare la ricerca. Tecnicamente questo permette di ridurre la ricorsione doppia, tipica degli algoritmi su alberi binari, ad una ricorsione singola.

L'algoritmo è il seguente:

Se l'albero è vuoto la ricerca termina subito con fallimento.
Se l'albero non è vuoto, si confronta il valore cercato con quello contenuto nella radice dell'albero:

Se i due valori coincidono la ricerca termina con successo.

Se il valore cercato è minore di quello contenuto nella radice la ricerca prosegue ricorsivamente nel sottoalbero sinistro.
Se è invece maggiore la ricerca prosegue nel sottoalbero destro.

Sulla complessità della ricerca

Si confrontino gli algoritmi di ricerca visti. In un albero binario, nel caso pessimo (ad esempio, se la chiave cercata non esiste) dobbiamo visitare tutti i nodi, quindi la complessità è lineare nel numero dei nodi.

In un albero binario di ricerca, ad ogni passo si visita un solo sottoalbero: infatti le due chiamate ricorsive compaiono nel metodo in rami mutuamente esclusivi. Di conseguenza nel caso pessimo la ricerca ha una complessità proporzionale alla massima profondità dell'albero.

Se l'ABR è bilanciato si dimostra che la sua profondità è logaritmica nel numero di nodi e quindi anche la complessità della ricerca diviene logaritmica.

Ad esempio, per scoprire che 45 non è presente nel seguente albero, con il primo algoritmo bisogna visitare 10 nodi, con il secondo solo tre.

Su di un albero ben bilanciato di 1000 nodi, il secondo algoritmo richiede al massimo una decina di passi.