Alberi

Ricerca rapida!

Gli alberi sono una struttura dati molto utilizzata in informatica perché permettono di memorizzare informazioni in modo dinamico, efficiente e ordinato (basta pensare che l'organizzazione dei sistemi operativi in cartelle è una struttura ad albero). Un albero è una struttura gerarchica in cui ogni elemento, eccetto uno, ha un solo elemento <<padre>> e tutti gli elementi possono avere elementi <<figli>>. L'unico elemento privo di padre è la <<radice>> dell'albero, mentre gli elementi privi di figli sono le <<foglie>>.

Albero generico

Concetti da tenere a mente:

Profondità o Livello
Altezza

La profondità riferita a un nodo è il numero di archi che congiunge il nodo stesso con la radice (la radice ha profondità 0).

Immaginando di ricavare la profondità di ogni nodo di un albero, allora l'altezza coincide con il valore più elevato di tali profondità (in pratica è il nodo più distante dalla radice).

Albero binario

L'albero binario allora è un particolare tipo di albero in cui ogni nodo può avere al massimo 2 figli. Più ampiamente utilizzato è l'albero binario di ricerca, chiamato così proprio perché è specializzato nella ricerca di un dato nodo. Per specializzato si intende che la ricerca risulta essere molto rapida poiché spesso comporta un uso minore di CPU per il computer. Si può capire quest'ultima affermazione con il seguente esempio:

Albero binario di ricerca (quindi ordinato)

Valore da cercare: 1 Confronti: 3
Valore da cercare: 3 Confronti: 2
Valore da cercare: 7 Confronti: 4
Valore da cercare: 8 Confronti: 1
Valore da cercare: 14 Confronti: 3

Array ordinato

Valore da cercare: 1 Confronti: 1
Valore da cercare: 3 Confronti: 2
Valore da cercare: 7 Confronti: 5
Valore da cercare: 8 Confronti: 6
Valore da cercare: 14 Confronti: 9

L'albero binario di ricerca risulta essere più conveniete rispetto a un array ordinato perché mi risparmia confronti, visto che a ogni confronto in realtà escludo più nodi (la cosa è più evidende con alberi con altezza maggiore).

Per realizzare un albero binario di ricerca occorrono una classe nodo, una classe albero e una classe contenente il main. La classe Nodo contiene le informazioni di un nodo e due puntatori a Nodo, la classe albero contiene le informazioni dell'albero e la radice.

Link albero binario di ricerca: https://mega.nz/#!SBETmaya!SPtf58194yZ0f1tjBg6fn2UDtoflO-MrgIPHL47oslI