Alberi

Albero radicato $T=(V,E)$ è una coppia di insiemi con le seguenti proprietà:

• $V$ è un insieme di nodi
• $E$ è un insieme di archi orientati che connette coppie di nodi di $V$
• un nodo di $V$ è la radice r dell’albero
• Ogni nodo, a parte la radice, ha esattamente un arco entrante
• Esiste un cammino unico dalla radice ad ogni nodo

title: Nice tip
L'albero per sua natura può anche essere espresso come una struttura ricorsivamente, dicendo che l'albero radicato è composto da un insieme vuoto, oppure da un nodo radice e uno o più sottoalberi, e la radice è connessa alla radice di tutti i sottoalberi da un arco orientato.

Primitive

1. father(x): ritorna il nodo padre di x
2. children(x): ritorna l’insieme dei nodi figli di x
3. sibling(x): ritorna l’insieme dei fratelli di x

Prodondità/livello di un nodo Lunghezza del cammino semplice dalla radice al nodo, misurata come numero di archi.

Altezza dell’albero Profondità massima delle foglie.

Tipi di albero

• Alberi binari
• Alberi generici

asd_19