Alberi

In questa pagina 6

Un albero è una collezione di nodi con struttura gerarchica padre-figlio, con i collegamenti strettamente necessari a tenerli connessi (una lista è il caso estremo). Applicazioni: dizionari e code con priorità (vedi Heap, Alberi binari di ricerca), file system, albero della ricorsione (vedi Algoritmi ricorsivi), alberi di decisione, codici di Huffman, alberi filogenetici.

Definizione

Un albero radicato $T$ è una collezione di nodi che, se non vuota, soddisfa:

esiste un nodo speciale $r$ , la radice;
ogni $v \ne r$ ha un unico padre $u$ ( $v$ è figlio di $u$ );
risalendo di padre in padre da ogni nodo si arriva a $r$ .

Definizione ricorsiva: $T = \{r\} \cup T_1 \cup \dots \cup T_k$ con $k \ge 0$ , dove $T_1, \dots, T_k$ sono alberi non vuoti le cui radici sono figlie di $r$ .

Terminologia

Termine	Significato
antenato di $y$	$x = y$ oppure $x$ antenato del padre di $y$
discendente di $y$	$x$ tale che $y$ è antenato di $x$
nodo interno	nodo con almeno un figlio
nodo esterno o foglia	nodo senza figli
sottoalbero $T_v$	$v$ con tutti i suoi discendenti
albero ordinato	per ogni nodo interno è fissato un ordine lineare tra i figli

Dato un albero ordinato, due nodi $u, v$ allo stesso livello: $u$ è a sinistra di $v$ se $u$ precede $v$ nella visita in preorder (vedi Visite di alberi).

Profondità, livello, altezza

Profondità $\text{depth}(v)$ = numero di antenati di $v$ meno 1; ricorsivamente: $\text{depth}(r) = 0$ , altrimenti $1 + \text{depth}(\text{padre}(v))$ .
Livello $i$ = insieme dei nodi a profondità $i$ .
Altezza di un nodo: $\text{height}(v) = 0$ se $v$ è foglia, altrimenti $1 + \max_{w \text{ figlio di } v} \text{height}(w)$ . Altezza dell'albero: $\text{height}(T) = \text{height}(r)$ .

Proposizione. Se $T$ non è vuoto, $\text{height}(T) = \max\{\text{depth}(v) : v \text{ foglia}\}$ .

Dimostrazione (induzione sull'altezza). Se $T$ è la sola radice, l'altezza è $0$ e l'unica foglia è $r$ , di profondità $0$ . Altrimenti $T = \{r\} \cup T_1 \cup \dots \cup T_k$ : ogni foglia di $T$ sta in un $T_i$ e ha profondità in $T$ pari a $1$ più la profondità in $T_i$ . Per ipotesi induttiva la massima profondità delle foglie di $T_i$ è $\text{height}(T_i)$ , quindi la massima profondità delle foglie di $T$ è $1 + \max_i \text{height}(T_i) = \text{height}(r)$ . $\square$

Interfaccia e implementazione

Metodi tipici: root(), parent(v), children(v), isRoot(v), isInternal(v), isExternal(v), size(). L'implementazione a struttura collegata dà a ogni nodo un riferimento al padre e alla collezione dei figli; spazio $\Theta(n)$ e children(v) in tempo proporzionale al numero di figli.

Algoritmi su profondità e altezza

Profondità (ricorsivo, risalendo):

Algoritmo depth(T, v)
Input: nodo v di T          Output: profondità di v
if T.isRoot(v) then return 0
else return 1 + depth(T, T.parent(v))

Costo $\Theta(\text{depth}(v) + 1)$ , al caso pessimo $\Theta(n)$ (albero ridotto a un cammino). Versione iterativa: si sale con un ciclo contando i passi.

Altezza di un nodo (dal basso, usando le altezze dei figli):

Algoritmo height(T, v)
Input: nodo v di T          Output: altezza di v
h <- 0
foreach w in T.children(v) do h <- max(h, 1 + height(T, w))
return h

Costo: $\text{height}$ è chiamato una volta per nodo; la chiamata su $u$ costa $\Theta(1 + c_u)$ con $c_u$ numero di figli. Poiché in un albero con $n$ nodi $\sum_{u} c_u = n - 1$ (ogni nodo non radice ha un solo padre), il totale è $\sum_u (1 + c_u) = 2n - 1 \in \Theta(n)$ . È una visita in postorder (vedi Visite di alberi).

Una strategia lenta ( $\text{heightBad}$ ). Calcolare l'altezza come massima depth tra le foglie, invocando depth da ciascuna foglia, è corretto per la proposizione ma costa $\Omega(n^2)$ . Istanza cattiva: un cammino di $n/2$ nodi con $n/2$ foglie attaccate al nodo più basso; ognuna delle $n/2$ foglie ha profondità $\ge n/2$ , e ogni chiamata a depth costa almeno questo: $\frac n2 \cdot \frac n2 = \frac{n^2}{4}$ operazioni.

Errori comuni

Confondere profondità e altezza di un nodo: la prima si conta dalla radice in giù, la seconda dalla foglia più lontana in su. In una foglia l'altezza è $0$ , la profondità no.
Dire che l'altezza dell'albero è il numero di nodi o di livelli: è il numero di archi del cammino più lungo (un albero con la sola radice ha altezza $0$ ).
Stimare height come $\Theta(n \cdot \text{figli})$ : il costo totale è $\Theta(n)$ perché $\sum c_u = n-1$ .

Versione ripasso

Albero radicato: radice $r$ ; ogni $v \ne r$ ha un unico padre; da ogni nodo si risale a $r$ . Ricorsivo: $T = \{r\} \cup T_1 \cup \dots \cup T_k$ .
Termini: antenato ( $x = y$ o antenato del padre), discendente, nodo interno ( $\ge 1$ figlio), foglia (nessun figlio), sottoalbero $T_v$ , albero ordinato (figli ordinati).
depth $(r) = 0$ , $\text{depth}(v) = 1 + \text{depth}(\text{padre})$ ; livello $i$ = nodi a profondità $i$ ; height(foglia) $= 0$ , $\text{height}(v) = 1 + \max_{w \text{ figlio}} \text{height}(w)$ .
Proposizione: $\text{height}(T) = \max\{\text{depth}(v) : v \text{ foglia}\}$ .
Algoritmi: depth ricorsivo $\Theta(\text{depth}+1) \le \Theta(n)$ ; height in postorder $\Theta(n)$ perché $\sum_u c_u = n-1$ (costo $\sum (1 + c_u) = 2n-1$ ); heightBad (depth da ogni foglia) $\Omega(n^2)$ : cammino di $n/2$ nodi con $n/2$ foglie in fondo.
Implementazione: struttura collegata (riferimento al padre e ai figli), spazio $\Theta(n)$ ; metodi root, parent, children, isRoot, isInternal, isExternal, size.
Algoritmi: depth(T,v): radice $\to 0$ , altrimenti $1 + \text{depth}(\text{parent})$ ; height(T,v): $h \leftarrow 0$ , per ogni figlio $w$ : $h \leftarrow \max(h, 1 + \text{height}(w))$ .
Errori: profondità vs altezza; altezza = numero di archi (radice sola $= 0$ ); costo di height non $\Theta(n \cdot \text{figli})$ . Vedi Visite di alberi.