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":
- parto dalla radice ma contiene "5" che non mi serve
- siccome "7" è più grande di "5" mi sposto sulla destra
- "9" non è quel che cerco ed è più grande di "7" e mi sposto sulla sinistra
- trovo "7", finito
Cerco "4":
- parto dalla radice ma contiene "5" che non mi serve
- siccome "4" è più piccolo di "5" mi sposto sulla sinistra
- "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"