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 e Ricorsione), alberi di decisione, codici di Huffman, alberi filogenetici.

Definizione

Definizione (albero radicato). 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$ .

Esempio. Un albero con radice $r$ , figli $a$ e $b$ e un nodo $c$ figlio di $a$ ha $n=4$ nodi; le foglie sono $b$ e $c$ .

La definizione ricorsiva è la stessa idea della ricorsione sui dati: un albero è una radice più alberi più piccoli, e per questo quasi tutte le dimostrazioni sugli alberi usano l'induzione (Principio di induzione, Dimostrazioni, induzione e invarianti) e quasi tutti gli algoritmi sono ricorsivi. Un albero è anche un caso particolare di grafo connesso e senza cicli (vedi Grafi - definizioni e proprietà); la lista concatenata (Liste concatenate) è l'albero in cui ogni nodo ha al più un figlio.

Albero di riferimento per gli esempi di questa pagina e di Visite di alberi: radice $r$ con figli $a, b$ ; $a$ ha figli $c, d$ ; $d$ ha figlio $e$ . Ha $n=6$ nodi, foglie $b, c, e$ .

Terminologia

Definizione (terminologia degli alberi)

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

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

Esempio. Nello stesso albero $r$ è antenato di $c$ , il sottoalbero $T_a$ è $\{a,c\}$ , $a$ è un nodo interno e $b$ , $c$ sono foglie.

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

Definizione (profondità, livello e 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)$ .

Esempio. Nello stesso albero $\text{depth}(c)=2$ , $\text{height}(a)=1$ e $\text{height}(T)=\text{height}(r)=2$ .

Sull'albero di riferimento ( $r$ ; $a,b$ figli di $r$ ; $c,d$ figli di $a$ ; $e$ figlio di $d$ ):

nodo	$r$	$a$	$b$	$c$	$d$	$e$
padre	—	$r$	$r$	$a$	$a$	$d$
profondità	0	1	1	2	2	3
altezza	3	2	0	0	1	0
figli $c_u$	2	2	0	0	1	0

La profondità si ottiene salendo (quanti archi fino alla radice), l'altezza scendendo (quanti archi fino alla foglia più lontana): $\text{height}(d)=1+\max\{\text{height}(e)\}=1+0=1$ , $\text{height}(a)=1+\max\{0,1\}=2$ , $\text{height}(r)=1+\max\{2,0\}=3$ . Livelli: livello $0=\{r\}$ , $1=\{a,b\}$ , $2=\{c,d\}$ , $3=\{e\}$ . La somma dei figli è $2+2+0+0+1+0=5=n-1$ .

Proposizione (altezza e profondità delle foglie). Se $T$ non è vuoto, $\text{height}(T) = \max\{\text{depth}(v) : v \text{ foglia}\}$ .

Esempio. Le foglie $b$ e $c$ hanno profondità $1$ e $2$ , quindi $\text{height}(T)=\max\{1,2\}=2$ . Sull'albero di riferimento le foglie $b,c,e$ hanno profondità $1,2,3$ e $\text{height}(T)=3$ .

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). L'uguaglianza $\sum_u c_u = n-1$ si vede contando gli archi in due modi: ogni arco collega un padre a un figlio, quindi il numero di archi è $\sum_u c_u$ ; ma ogni nodo tranne la radice ha esattamente un padre, cioè esattamente un arco che lo collega verso l'alto, quindi gli archi sono $n-1$ . Sull'albero di riferimento: $\sum_u(1+c_u)=6+5=11=2\cdot6-1$ chiamate-passi.

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 (per $n=40$ : $20$ foglie a profondità $\ge 20$ , quindi $\ge 400$ passi contro i $2n-1=79$ di height). Il grafico confronta le due crescite: la prima è quadratica (si veda Notazione asintotica), la seconda lineare.

Grafico interattivo: Costo di heightBad sull'istanza cattiva (almeno n²/4 passi) contro height (2n − 1 passi): a n = 40 sono 400 contro 79, e il rapporto cresce con n

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; risalendo da ogni nodo si arriva a $r$ . Definizione ricorsiva: $T = \{r\} \cup T_1 \cup \dots \cup T_k$ , con $k \ge 0$ .
Terminologia: antenato di $y$ ( $x = y$ oppure antenato del padre di $y$ ); discendente; nodo interno (almeno un figlio); foglia (nessun figlio); sottoalbero $T_v$ ; albero ordinato (ordine fisso tra i figli).
Profondità: $\text{depth}(r) = 0$ , $\text{depth}(v) = 1 + \text{depth}(\text{padre}(v))$ . Livello $i$ : nodi a profondità $i$ .
Altezza: $\text{height}(v) = 0$ se $v$ è foglia, altrimenti $1 + \max_{w \text{ figlio di } v} \text{height}(w)$ . Altezza dell'albero: $\text{height}(r)$ , cioè il numero di archi del cammino più lungo.
Proposizione: $\text{height}(T) = \max\{\text{depth}(v) : v \text{ foglia}\}$ , per induzione sull'altezza.
Somma dei figli: $\sum_u c_u = n - 1$ , perché ogni nodo non radice ha un solo padre.
Interfaccia: root, parent, children, isRoot, isInternal, isExternal, size. Struttura collegata: spazio $\Theta(n)$ .
Algoritmi (vedi Visite di alberi):
- depth(T,v): radice $\to 0$ , altrimenti $1 + \text{depth}(\text{parent})$ ; costo $\Theta(\text{depth}(v)+1)$ , al caso pessimo $\Theta(n)$ ;
- height(T,v): $h \leftarrow 0$ , per ogni figlio $w$ : $h \leftarrow \max(h, 1 + \text{height}(w))$ ; postorder con costo $\sum_u (1 + c_u) = 2n - 1 \in \Theta(n)$ ;
- heightBad (depth chiamato da ogni foglia): $\Omega(n^2)$ sul cammino di $n/2$ nodi con $n/2$ foglie in fondo; per $n = 40$ almeno $400$ passi contro $79$ .
Albero di riferimento: radice $r$ con figli $a, b$ ; $a$ ha figli $c, d$ ; $d$ ha figlio $e$ . Ha $n = 6$ nodi, foglie $b, c, e$ , altezza $3$ ; profondità $0,1,1,2,2,3$ .
Somma dei figli sull'albero di riferimento: $2+2+0+0+1+0 = 5 = n-1$ . Costo di height sullo stesso albero: $\sum_u (1 + c_u) = 11 = 2n-1$ .
Errori tipici: profondità (dalla radice in giù) contro altezza (dalla foglia in su); altezza uguale al numero di nodi o di livelli (è il numero di archi, radice sola $= 0$ ); stimare height come $\Theta(n \cdot \text{figli})$ .