Alberi binari

Un albero binario è un albero ordinato (vedi AlberiAlbero radicato (definizione per padre e ricorsiva), terminologia (antenati, discendenti, nodi interni ed esterni, sottoalbero, albero ordinato), profondità, livello, altezza; altezza = massima profondità delle foglie; algoritmi depth e height con costo; somma dei figli = n-1; esempio di algoritmo Omega(n^2) (heightBad).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.

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.

Le 3, 4 e 5 sono corollari della 1 e della 2.

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$ di $i_1, i_2$ nodi interni, $i = i_1 + i_2 + 1$. 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$, 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; in totale $m \ge h + 2 = (h+1) + 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).

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

Oltre a preorder e postorder (vedi Visite di alberiVisite in preorder e postorder come schemi generali (template) da adattare; complessità Theta(n + somma dei costi di visita) perché la somma dei figli è n-1; esempi (indice di un libro, spazio occupato in un file system); profondità con il preorder, altezza con il postorder; antenato comune più basso.Visite di alberi →), negli alberi binari si ha la visita inorder: prima il figlio sinistro, poi il padre, poi il figlio destro.

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 ricercaAlbero binario di ricerca come albero binario proprio con entry nei nodi interni e foglie vuote; inorder crescente; TreeSearch; get, put e remove (due casi, con predecessore inorder) in Theta(h); altezza fino a n-1; esempi di inserimenti; alberi aumentati con campi size e max e algoritmi di conteggio e interrogazione in O(h).Alberi binari di ricerca →).

Espressioni aritmetiche e parse tree

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.

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$.

Esempio: 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)

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$. 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.