Alberi

0️⃣ Definizione

In informatica, un albero o struttura ad albero (tree in inglese) è la struttura dati che si riconduce al concetto di albero con radice presente nella teoria dei grafi. Un albero si compone di due tipi di sottostrutture fondamentali: il nodo, che in genere contiene informazioni, e l'arco, che stabilisce un collegamento gerarchico fra due nodi: si parla allora di un nodo padre dal quale esce un arco orientato che lo collega ad un nodo figlio.

L'unico elemento privo di arco ascendente Ia radice dell'albero, mentre gli elementi privi di archi discendenti sono Ie foglie.

1️⃣ Alberi generici

Un albero è un insieme non vuoto di nodi e di archi tale che sia:

connesso, cioè presi due nodi qualsiasi esista un percorso semplice tra di essi;

aciclico, ovvero non esista alcun percorso semplice in cui il nodo iniziale e quello finale siano coincidenti.

Per percorso semplice si intende una sequenza di coppie di nodi distinti collegate da un arco che rappresenta un cammino sugli archi dell'allbero.

rappresenta un albero in cui è evidenziato il percorso semplice *(d, a), (a, b), (b, g)* dal nodo d al nodo g passando per i nodi a e b

Alcune definizioni

Nodo padre: Un nodo padre è un nodo che ha almeno un nodo figlio collegato ad esso. In altre parole, è un nodo che si trova ad un livello superiore rispetto ad uno o più nodi figli nella gerarchia dell'albero.

Nodo figlio: Un nodo figlio è un nodo che ha un nodo padre collegato ad esso. Ogni nodo figlio si trova ad un livello immediatamente inferiore rispetto al suo nodo padre nella gerarchia dell'albero.

Foglia: Una foglia è un nodo che non ha nodi figli collegati ad esso. In altre parole, è un nodo terminale che non si ramifica ulteriormente. Le foglie sono i nodi finali o estremi nell'albero.

Radice: La radice è il nodo superiore nell'albero da cui si diramano tutti gli altri nodi. È l'unico nodo che non ha un nodo padre. Ogni albero ha una sola radice.

Il nodo b è il padre dei nodi *e, f,* e g; il nodo c è padre dei nodi h e i; il noo d è padre del nodo i; il nodo a è padre dei nodi *b, c* e d. I nodi *e, f, g, h, i* ed l sono le foglie dell'albero.

Altre Definizioni

Profondità: La profondità di un nodo in un albero rappresenta la lunghezza del percorso dal nodo radice a quel nodo specifico. In termini semplici, la profondità indica il livello a cui si trova un nodo all'interno della struttura gerarchica dell'albero. La radice ha una profondità di 0, mentre ogni livello successivo aumenta la profondità di 1.

Livello: Il livello di un nodo in un albero indica la distanza tra quel nodo e la radice dell'albero. La radice si trova al livello 0, i nodi direttamente collegati alla radice sono al livello 1, i loro nodi figli sono al livello 2 e così via. In pratica, il livello di un nodo è determinato dalla lunghezza del percorso che collega il nodo alla radice.

Sottoalberi: Un sottoalbero è una porzione dell'albero che deriva da un nodo e include quel nodo e tutti i suoi discendenti. In altre parole, un sottoalbero è formato da un nodo (chiamato radice del sottoalbero) e da tutti i nodi che hanno come nodo padre un nodo appartenente al sottoalbero. Ogni nodo in un albero può avere uno o più sottoalberi associati ad esso.

Ogni nodo dell'albero ha tre componenti:

Info (componente informativa);

pfc (pointer first child, riferimento al primo figlio);

pfs (pointer first sibling. riferimento al primo fratello).

2️⃣ Alberi Binari

Gli alberi binari estendono le caratteristiche degli alberi generici, in particolare: un albero binario (BT, Binary Tree) un albero in cui nodo ha al massuno due figli, denominati rispettivamente figlio sinistro e figlio destro.

Un albero binario di ricerca si dice bilanciato se l'albero stesso e ogni suo sottoalbero hanno un numero di nodi presenti nel sottoalbero sinistro che differisce al più di 1 dal numero di nodi del sottoalbero destro.
In un albero binario di ricerca bilanciato con n nodi la profondità di una foglia, cioé la sua distanza dalla radice, è al massimo: