Alberi binari

In questa pagina 5

Definizione (albero binario e albero binario proprio). Un albero binario è un albero ordinato (vedi Alberi) in cui ogni nodo interno ha al più 2 figli, ogni nodo non radice è etichettato come figlio sinistro o destro del padre, e il figlio sinistro precede il destro. Se c'è un solo figlio si assume sia il sinistro. Il sottoalbero sinistro (destro) di $v$ è quello radicato nel suo figlio sinistro (destro).

Un albero binario è proprio (o pieno, full) se ogni nodo interno ha esattamente 2 figli. Un albero binario è un caso particolare di albero (Alberi) e di grafo senza cicli (Grafi - definizioni e proprietà); le interfacce sono ADT (Tipi di dato astratti).

Esempio. Un albero con la radice, un figlio sinistro con due foglie e un figlio destro foglia è binario proprio: ogni nodo interno ha $2$ figli e $n=5$ .

interfaccia BinaryTree estende Tree:
    left(p)    figlio sinistro di p (null se non esiste)
    right(p)   figlio destro di p (null se non esiste)
    sibling(p) fratello di p (null se non esiste)

Relazioni in un albero binario proprio non vuoto

Siano $n$ i nodi, $m$ le foglie (quindi $n - m$ i nodi interni) e $h$ l'altezza.

Teorema (relazioni in un albero binario proprio)

# Relazione

1 $m = (n - m) + 1$

2 $h + 1 \le m \le 2^h$

3 $h \le n - m \le 2^h - 1$

4 $2h + 1 \le n \le 2^{h+1} - 1$

5 $\log_2(n+1) - 1 \le h \le \frac{n-1}{2}$

Esempio. Albero perfetto di altezza $h=2$ : $n=2^3-1=7$ , $m=2^2=4$ foglie e $n-m=3=m-1$ .

Le 3, 4 e 5 sono corollari della 1 e della 2. Valori per $h = 0,\dots,4$ (intervalli possibili per foglie e nodi):

$h$	foglie $m$ : da $h+1$ a $2^h$	nodi $n$ : da $2h+1$ a $2^{h+1}-1$
0	1	1
1	2	3
2	da 3 a 4	da 5 a 7
3	da 4 a 8	da 7 a 15
4	da 5 a 16	da 9 a 31

Dimostrazione della 1 (induzione sul numero di nodi interni $i = n - m$ ). Se $i = 0$ l'albero è una sola foglia: $m = 1 = 0 + 1$ . Altrimenti la radice è interna con sottoalberi propri $T_1, T_2$ (non vuoti, perché l'albero è proprio) di $i_1, i_2$ nodi interni, $i = i_1 + i_2 + 1$ (i nodi interni dei due sottoalberi più la radice stessa). Per ipotesi $m_1 = i_1 + 1$ , $m_2 = i_2 + 1$ , quindi $m = m_1 + m_2 = i_1 + i_2 + 2 = i + 1$ . $\square$

Dimostrazione di $m \le 2^h$ (induzione sull'altezza). Base $h = 0$ : una sola foglia, $1 = 2^0$ . Passo: $T$ di altezza $h+1$ ha radice con sottoalberi $T_1, T_2$ di altezze $h_1, h_2 \le h$ , e $h + 1 = \max(h_1, h_2) + 1$ . Per ipotesi $m_i \le 2^{h_i} \le 2^h$ (la seconda disuguaglianza perché $h_i \le h$ e $2^x$ è crescente: Esponenziale e logaritmo), quindi $m = m_1 + m_2 \le 2 \cdot 2^h = 2^{h+1}$ . $\square$

Dimostrazione di $m \ge h + 1$ (induzione sull'altezza). Base $h = 0$ : $m = 1$ . Passo: uno dei sottoalberi ha altezza $h$ e per ipotesi almeno $h + 1$ foglie; l'altro ha almeno $1$ foglia (ogni albero non vuoto ne ha una); in totale $m \ge (h+1) + 1 = h + 2$ , che è la tesi per un albero di altezza $h+1$ . $\square$

Corollari. Dalla 1, $n - m = m - 1$ , quindi $h \le n - m \le 2^h - 1$ (relazione 3) e $n = m + (n - m) = 2m - 1$ , da cui $2(h+1) - 1 = 2h + 1 \le n \le 2^{h+1} - 1$ (relazione 4). Da $n \le 2^{h+1} - 1$ si ottiene $h \ge \log_2(n+1) - 1$ e da $n \ge 2h + 1$ si ottiene $h \le \frac{n-1}{2}$ (relazione 5). Passaggi: $n \le 2^{h+1}-1 \iff n+1 \le 2^{h+1}$ , e applicando $\log_2$ (funzione crescente, Esponenziale e logaritmo) a entrambi i membri $\log_2(n+1) \le h+1$ ; analogamente $2h+1 \le n \iff h \le \frac{n-1}{2}$ . Il grafico mostra i due limiti: ogni albero binario proprio con $n$ nodi ha l'altezza tra le due curve.

Grafico interattivo: Altezza di un albero binario proprio con n nodi: limite inferiore log2(n+1) − 1 (albero perfetto) e limite superiore (n − 1)/2 (albero a pettine); per n = 31 l'altezza è tra 4 e 15

Casi estremi. $m = 2^h$ : albero perfetto (tutti i livelli pieni), $n = 2^{h+1} - 1$ , $h = \log_2(n+1) - 1$ . $m = h + 1$ : ogni nodo interno ha almeno una foglia come figlio ("a pettine"), $n = 2h + 1$ , $h = \frac{n-1}{2}$ . Quindi in un albero binario proprio l'altezza è almeno logaritmica ma può essere lineare nel numero di nodi. (Verifica: le relazioni 1-5 sono state controllate su 2000 alberi casuali.)

Visita inorder

Definizione (visita inorder). Oltre a preorder e postorder (vedi Visite di alberi), negli alberi binari si ha la visita inorder: prima il figlio sinistro, poi il padre, poi il figlio destro.

Esempio. Sull'albero con radice $+$ e foglie $3$ e $4$ la visita inorder dà $3,+,4$ .

Algoritmo inorder(T, v)
if T.left(v) != null then inorder(T, T.left(v))
visita v
if T.right(v) != null then inorder(T, T.right(v))

Costo $\Theta(n + \sum t_u)$ come le altre visite. In un albero binario di ricerca la visita inorder tocca le chiavi in ordine crescente (vedi Alberi binari di ricerca).

Espressioni aritmetiche e parse tree

Definizione (parse tree di un'espressione). Un'espressione fully parenthesized in notazione infissa è una costante/variabile $a$ oppure $(E_1\ \text{Op}\ E_2)$ con $E_1, E_2$ fully parenthesized e Op binario. Il parse tree è l'albero binario proprio che ha nelle foglie costanti e variabili, nei nodi interni gli operatori, con sottoalbero sinistro e destro uguali ai parse tree di $E_1$ ed $E_2$ ; le parentesi sono implicite nella struttura. Con operatori unari l'albero non è più proprio. Le espressioni aritmetiche e la precedenza degli operatori sono quelle di Tipi numerici ed espressioni (Fondamenti di Informatica); la costruzione del parse tree è una fase della compilazione (Paradigmi di programmazione e linguaggi, Dal programma C all'eseguibile ARM).

Esempio. $((15+x)\cdot(7-(9\div3)))$ con $x=5$ vale $20\cdot4=80$ .

Esempio: $((15 + x) \cdot (7 - (9 \div 3)))$ ha radice $\cdot$ , figlio sinistro $+$ con foglie $15, x$ , figlio destro $-$ con foglie $7$ e il nodo $\div$ con foglie $9, 3$ . I compilatori costruiscono il parse tree e lo usano per controllo dei tipi, ottimizzazioni e generazione del codice.

Valutazione, postorder: ogni operatore ha bisogno dei valori dei figli.

Algoritmo evaluateExpression(T, v)
Input: parse tree T, nodo v      Output: valore dell'espressione di T_v
if T.isInternal(v) then
    op <- v.getElement()
    x <- evaluateExpression(T, T.left(v))
    y <- evaluateExpression(T, T.right(v))
    return x op y
else return v.getElement()

Costo $\Theta(n)$ ( $t_u$ costante). Con $x = 5$ l'esempio vale $(15+5)\cdot(7 - 9/3) = 20 \cdot 4 = 80$ . Traccia del postorder (i valori risalgono dalle foglie): $15 + x = 20$ ; $9 \div 3 = 3$ ; $7 - 3 = 4$ ; $20 \cdot 4 = 80$ . La visita inorder dello stesso albero dà $15,+,x,\cdot,7,-,9,\div,3$ , cioè l'espressione senza parentesi: perde l'informazione sull'ordine delle operazioni, che solo la struttura dell'albero conserva.

Esempio: heightSum

Definizione (heightsum). La heightsum di un albero binario proprio è la somma delle altezze di tutti i suoi nodi. Con la sola somma restituita da ogni sottoalbero non si potrebbe calcolare l'altezza del padre; si restituisce quindi una coppia (somma, altezza):
Algoritmo heightSum(T, v)
Input: v in T      Output: (somma delle altezze dei nodi di T_v, altezza di v)
if T.isExternal(v) then return (0, 0)
(sL, hL) <- heightSum(T, T.left(v))
(sR, hR) <- heightSum(T, T.right(v))
h <- max(hL, hR) + 1
return (sL + sR + h, h)

Esempio. In un albero con la radice, un figlio sinistro con due foglie e un figlio destro con una foglia e un nodo con due foglie, le altezze dei nodi interni sono $3,1,2,1$ e la heightsum vale $7$ .

Costo $\Theta(n)$ (postorder). Per l'albero con radice che ha un figlio sinistro con due foglie e un figlio destro con una foglia e un nodo con due foglie, le altezze dei nodi interni sono $3, 1, 2, 1$ e la heightsum è $7$ . Traccia dell'algoritmo, coppia (somma, altezza) di ogni sottoalbero: ogni foglia dà $(0,0)$ ; il figlio sinistro della radice, con due foglie, dà $h=\max(0,0)+1=1$ e somma $0+0+1=1$ , cioè $(1,1)$ ; il nodo con due foglie nel sottoalbero destro dà ancora $(1,1)$ ; il figlio destro, con una foglia $(0,0)$ e quel nodo $(1,1)$ , dà $h=\max(0,1)+1=2$ e somma $0+1+2=3$ , cioè $(3,2)$ ; la radice, con $(1,1)$ a sinistra e $(3,2)$ a destra, dà $h=\max(1,2)+1=3$ e somma $1+3+3=7$ , cioè $(7,3)$ . Lezione generale: per ottenere una strategia efficiente conviene spesso calcolare un'informazione più ricca di quella richiesta (qui l'altezza oltre alla somma).

Errori comuni

Applicare le relazioni 1-5 ad alberi non propri: valgono (con altre costanti) solo per alberi propri.
Confondere $2^h$ (massimo numero di foglie) con $2^{h+1} - 1$ (massimo numero di nodi).
Usare un preorder per valutare un'espressione: i valori dei figli servono prima.
Calcolare heightSum chiamando height da ogni nodo: diventa quadratico nel caso pessimo.

Versione ripasso

Albero binario: ogni nodo ha al più $2$ figli, ordinati (il figlio unico è il sinistro). Proprio (full): ogni nodo interno ha esattamente $2$ figli. Interfaccia BinaryTree: left(p), right(p), sibling(p) (vedi Alberi, Tipi di dato astratti).
Relazioni (proprio, non vuoto, $n$ nodi, $m$ foglie, altezza $h$ ):

#	Relazione
1	$m = (n - m) + 1$
2	$h + 1 \le m \le 2^h$
3	$h \le n - m \le 2^h - 1$
4	$2h + 1 \le n \le 2^{h+1} - 1$
5	$\log_2(n+1) - 1 \le h \le \frac{n-1}{2}$

Prove:
- (1) induzione sui nodi interni $i = n - m$ : $m = (i_1 + 1) + (i_2 + 1) = i + 1$ ;
- $m \le 2^h$ per induzione sull'altezza: $m = m_1 + m_2 \le 2 \cdot 2^h$ ;
- $m \ge h + 1$ : un sottoalbero ha altezza $h$ (almeno $h+1$ foglie), l'altro almeno $1$ foglia;
- (3), (4), (5) da $n - m = m - 1$ e $n = 2m - 1$ , applicando $\log_2$ a $n + 1 \le 2^{h+1}$ .
Esempio: perfetto di altezza $h = 2$ : $n = 7$ , $m = 4$ , $n - m = 3$ .
Casi estremi: $m = 2^h$ albero perfetto ( $n = 2^{h+1} - 1$ ); $m = h + 1$ albero a pettine ( $n = 2h + 1$ ). Altezza almeno logaritmica, al più lineare.
Inorder: sinistro, padre, destro; costo $\Theta(n + \sum t_u)$ ; in un albero di ricerca dà le chiavi crescenti (vedi Alberi binari di ricerca).
Parse tree: foglie = costanti e variabili, nodi interni = operatori. Esempio $((15 + x) \cdot (7 - (9 \div 3)))$ con $x = 5$ vale $20 \cdot 4 = 80$ . L'inorder dà $15,+,x,\cdot,7,-,9,\div,3$ : perde l'ordine delle operazioni.
evaluateExpression: postorder; nodo interno: x <- eval(left), y <- eval(right), return x op y; foglia: il suo valore. Costo $\Theta(n)$ (vedi Visite di alberi).
heightSum: postorder che restituisce la coppia (somma, altezza); foglia $\to (0,0)$ ; h <- max(hL,hR)+1; return (sL+sR+h, h). Costo $\Theta(n)$ . Esempio: altezze interne $3,1,2,1$ , heightsum $7$ . Conviene calcolare un'informazione più ricca di quella richiesta.
Altezza: $\log_2(n+1) - 1 \le h \le \frac{n-1}{2}$ . L'albero perfetto ha $h = \log_2(n+1)-1$ , quello a pettine $h = \frac{n-1}{2}$ .
Visita inorder: su un albero con radice $+$ e foglie $3$ e $4$ dà $3,+,4$ ; costo $\Theta(n + \sum t_u)$ .
Verifica: le relazioni 1-5 sono state controllate su $2000$ alberi casuali; come per ogni relazione, valgono solo per alberi propri.
Errori tipici: applicare le relazioni ad alberi non propri; confondere $2^h$ foglie con $2^{h+1} - 1$ nodi; usare il preorder per valutare un'espressione; chiamare height da ogni nodo in heightSum (diventa quadratico).