alberi

In alcuni casi serve rappresentare una informazione che non ha una struttura lineare come ad esempio quella di file e cartelle o la discendenza di un cavallo in un allevamento. In questi casi ci vengono in aiuto gli alberi, strutture dati che potremmo rappresentare in questo modo:

Come è evidente dal diagramma ogni elemento non ha un solo successivo come nel caso delle liste, le diverse parti di un albero hanno un nome specifico:

nodo

sono le parti dell'albero che contengono le informazioni (le ellissi nell'esempio)

arco

una delle frecce che collega un nodo con un altro nodo (hanno una direzione: l'arco blu collega il nodo 1 con il 2 ma non viceversa)

radice

è il nodo da cui è possibile raggiungere tutti gli atri percorrendo una serie di archi (quello rosso nell'esempio)

foglia

un nodo che non ha discendenti (tutti quelli verdi nell'esempio)

nodo padre

nodo da cui parte un arco (ad esempio il nodo 4 è padre dell'8)

nodo figlio

nodo a cui arriva un arco (ad esempio il nodo 8 è figlio del 4)

In un albero non è possibile avere dei percorsi chiusi (un arco da 10 a 4 formerebbe un percorso chiuso 4→7→10→4) ne molteplici alternative per arrivare allo stesso nodo (come ad esempio se mettessi un arco da 6 a 9, dalla radice per arrivare a 9 avrei 1→4→7→9 oppure 1→4→6→9).

Alberi binari

Quelli di cui ci occuperemo sono un particolare tipo di alberi detti alberi binari ordinati (o alberi binari di ricerca): la loro particolarità è che ogni nodo ha al massimo due figli e le informazioni vengono inserire seguendo queste regole:

• all'inizio inserisco l'informazine nella radice
• quando devo inserire un dato ulteriore inizio guardando dalla radice:
  • se il dato da inserire è minore del valore presente nel nodo che sto valutando (la radice all'inizio) lo inserirò come suo figlio sinistro se non ce ne è già uno in caso ci sia già riapplico lo stesso ragionamento guardando il figlio sinistro
  • se il dato da inserire è maggiore del valore presente nel nodo che sto valutando (la radice all'inizio) lo inserirò come suo figlio destro se non ce ne è già uno in caso ci sia già riapplico lo stesso ragionamento guardando il figlio destro

Ricerca in un albero binario ordinato

• se l'elemento che cerco è nella radice ho finito
• altrimenti inizio guardando dalla radice e:
  • se l'elementoi che cerco è più piccolo di quello presente nel nodo che sto guardando se il figlio sinistro non c'è l'elemento non esiste altrimenti riapplico il ragionamanto guardando il figlio sinistro
  • se l'elementoi che cerco è più grande di quello presente nel nodo che sto guardando se il figlio destro non c'è l'elemento non esiste altrimenti riapplico il ragionamanto guardando il figlio destro

Proviamo a vedere che succede facendo due ricerce nell'albero di esempio qui sotto:

Cerco "7":

1. parto dalla radice ma contiene "5" che non mi serve
2. siccome "7" è più grande di "5" mi sposto sulla destra
3. "9" non è quel che cerco ed è più grande di "7" e mi sposto sulla sinistra
4. trovo "7", finito

Cerco "4":

1. parto dalla radice ma contiene "5" che non mi serve
2. siccome "4" è più piccolo di "5" mi sposto sulla sinistra
3. "3" non è quel che cerco ed è più piccolo di "4" e mi dovrei spostare a destra ma siccome il figlio destro non c'è: questo albeo non contine il valore "4"