Alberi

Un albero radicato è un digrafo aciclico $T=(N,A)$ con un insieme finito di nodi $N$ e archi $A\subseteq N\times N$.

Ogni nodo di un albero $T$ ha uno e un solo padre, eccetto per la radice $r\in N$: $$\forall v\in N\setminus \{r\},\exists !u\in N:(u,v)\in A$$

Su questo tipo di dato ci si aspettano le operazioni:

• padre(Tree P, Node v) -> Node | NIL che assume v presente in P e restituisce NIL se è radice
• figli(Tree P, Node v) -> [Node] che assume v presente in P

Per esempio, con

si ha $N=\{a,b,c\}$ e $A=\{(a,b),(a,c)\}$ che ha radice $a$.

Caratteristiche

Tra i nodi sono definiti dei cammini $(n_0,...,n_k)$ da un nodo $u$ a $u^{\prime }$, se: $$u=n_0\wedge u^{\prime }=n_k\wedge (n_{i-1},n_i)\in A,\forall i=1,...,k$$ la cui lunghezza è il numero di archi $k$, di conseguenza esisterà sempre un cammino lungo $0$, i.e. da $u$ a $u$.

Inoltre, tra le caratteristiche di un albero sono definite anche:

• Un nodo $n\in N$ è detto foglia se $\nexists v\in N:(n,v)\in A$
• Tutti i nodi che non sono foglie sono detti nodi interni
• Viene detto grado il numero di figli di un nodo
• I nodi con lo stesso padre sono detti fratelli
• Un nodo $y$, nel cammino dalla radice $r$ a $x$, è detto antenato di $x$, mentre $x$ è il suo discendente
• Se $y$ è antenato di $x$ e $y\ne x$ allora $y$ è antenato proprio di $x$, mentre $x$ discendente proprio
• Un sottoalbero di radice $x\in N$ è formato dai discendenti di $x$
• La profondità di un nodo $x$ è la lunghezza del cammino dalla radice a $x$
• Un livello è l'insieme dei nodi con la stessa profondità
• L'altezza di un nodo $x$ è la lunghezza del cammino più lungo da $x$ ad una foglia
• L'altezza dell'albero è l'altezza della radice, che corrisponde alla profondità massima

Per esempio, con

si ha che:

• $7$ e $3$ sono nodi interni mentre $8$, $12$ e $10$ sono foglie
• $7$ ha grado $2$, altezza $2$ e profondità $0$
• $3$ e $7$ sono antenati propri di $12$, mentre $12$ è discendente di $3$, $7$ e $12$
• $8$ e $12$ hanno profondità $2$, mentre $10$ profondità $1$
• $3$ e $10$ come $8$ e $12$ sono fratelli
• $\{7\}$ è al livello $0$, $\{3,10\}$ al livello $1$ e $\{8,12\}$ al livello $2$
• $(7,3)$, $(7,3,12)$, $(7,10)$ e $(8,8)$ sono alcuni dei possibili cammini
• $(\{3,8,12\},\{(3,8),(3,12)\})$ è sottoalbero con radice $3$

Alberi $k$-ari

Un albero si dice $k$-ario se ogni nodo ha al più $k$ figli. È detto binario invece, se è vuoto o possiede ricorsivamente un sottoalbero binario sinistro e uno destro, ovvero $k=2$ figli.

Un albero $k$-ario è definito bilanciato se l'altezza $h=O(\log n)$.

Se è bilanciato, viene anche detto completo se ogni foglia ha la stessa profondità e ogni nodo ha grado $k$.

Per esempio, l'albero

è $3$-ario perchè ha $k$ che è al minimo $3$, bilanciato ma non completo.

Numero di nodi

Si può dimostrare che, se l'albero è $k$-ario completo con altezza $h$, il numero di foglie sarà: $$n=k^h$$ per induzione su $h$:

• Caso base: per $h=0$ ci sono $k^0=1$ foglie, cioè la radice
• Passo induttivo: si assume che $k^{h-1}$ sia il numero foglie dell'albero alto $h-1$, allora dato che ogni sua foglia ha a sua volta $k$ foglie, per ipotesi induttiva $k^{h-1}\cdot k=k^h$

da cui si ricava che l'altezza sarà $h={\log }_{k}n$.

Inoltre, si può anche derivare che il numero di nodi interni è: $$\sum _{i=0}^{n-1}{k}^i\underset{k\ne 1}{=}\frac{k^h-1}{k-1}$$ cioè la somma del numero di foglie per altezza crescente.