Alberi binari: definizione e alcune proprietà

1 Alberi binari
Definizione 1.1 (Alberi binari) Un albero binario è un insieme finito di nodi. L’insieme può essere
vuoto (nel qual caso diciamo che l’albero è vuoto) oppure non vuoto. Un albero non vuoto deve
soddisfare le seguenti proprietà

• contiene un nodo speciale detto radice

• ad ogni nodo possiamo associare (al più) due figli detti rispettivamente figlio sinistro e figlio
destro. Se un nodo n è figlio di un nodo m, allora diciamo che m è padre di n.

• ogni nodo, tranne la radice, ha esattamente un padre. La radice è l’unico nodo che non ha
un padre

Un cammino da un nodo un nodo n ad un nodo m è una sequenza di nodi connessi da archi

che portano da n ad m. Sia n un nodo di un albero binario T con radice r. Un qualsiasi nodo m
lungo un cammino dalla radice r ad n è detto antenato di m. Se m è antenato di n, allora n è un
discendente di m (ogni nodo è antenato e discendente di se stesso).

Un nodo di un albero binario si dice nodo esterno o, pù semplicemente, foglia se non ha figli
(entrambi i sottoalberi di cui è radice sono vuoti). Un nodo di un albero binario si dice interno se
ha almeno un figlio.

2 7

3 5 8

4 6 9

Figure 1: Un albero binario

Si consideri l’albero binario in Figura 1. Il nodo 6 è un discendente del nodo 2; il nodo 2, cosı̀
come i nodi 1 e 5 sono antenati di 6. I nodi 4 6 e 9 sono delle foglia, tutti gli altri nodi sono dei
nodi interni.
In un albero binario, la profondità di un nodo è la lunghezza di un cammino dalla radice al nodo
(cioè il numero di archi tra la radice ed il nodo). La profondità massima di un nodo all’interno di
un albero è detta altezza dell’albero.

1
 1 profondità 0

2 7 profondità 1

altezza =3
3 5 8 profondità 2

4 6 9 profondità 3

Figure 2: Un albero binario di altezza 3

1.1 Alberi binari completi e quasi completi

Definizione 1.2 (Alberi binari completi) Il grado di un nodo è il numero di figli di quel nodo.
Un albero binario si dice completo se:

1. tutte le foglie hanno la stessa altezza h;

2. tutti i nodi interni hanno grado 2 (hanno esattamente due figli).

Definizione 1.3 (Alberi binari quasi completi) Un albero binario si dice quasi completo se tutti
i livelli, tranne al più l’ultimo, sono completi; nell’ultimo livello possono mancare alcune foglie
consecutive a partire dall’ultima foglia a destra.

Alcuni esempi di alberi binari quasi completi sono riportati in Figura 3-(a) e (b). In Figura 3-(c)
abbiamo invece un esempio di albero binario non quasi completo.

(a) (b)

(c)

Figure 3: Alberi Binari quasi completi

1.2 Proprietà degli alberi binari completi e quasi completi

Proposizione 1.4 Un albero binario completo di altezza h ha 2h+1 − 1 nodi.

2
Dimostrazione: La prova è per induzione su h.
- Caso base (h = 0). Un albero binario completo di altezza h = 0 ha un solo nodo (la radice).
Inoltre, 20+1 − 1 = 1. Quindi il caso base è verificato.

- Passo induttivo: (h > 1). Assumiamo (per ipotesi induttiva) che un albero binario completo
di altezza h abbia 2h+1 − 1 nodi, e dimostriamo che un albero binario T completo e di altezza
h + 1 ha 2(h+1)+1 − 1 = 2h+2 − 1 nodi. Come è fatto T ? Ha la radice, più un sottoalbero
sinistro Ts e un sottoalbero destro Td entrambi completi e di altezza h. Per ipotesi induttiva
#nodi (Td ) = #nodi (Ts ) = 2h+1 − 1. Quindi:

#nodi (T ) = 1 + #nodi (Ts ) + #nodi (Td ) = 1 + (2h+1 − 1) + (2h+1 − 1) = (2 · 2h+1 ) − 1 = 2h+2 − 1

Esercizio 1.5 Dimostrate per induzione su h che un albero binario completo di altezza h ha 2h
foglie.

Nel seguito cercheremo di stabilire alcune utili proprietà degli alberi binari quasi completi.
Innanzitutto, vediamo la relazione che esiste tra il numero di nodi e l’altezza di un albero binario
quasi completo.

Proposizione 1.6 Sia T un albero binario quasi completo di altezza h. Allora: 2h ≤ #nodi (T ) ≤
2h+1 − 1.

Dimostrazione: Per dimostrare questo risultato abbiamo bisogno di determinare il numero min-
imo ed il numero massimo che un albero binario quasi completo di altezza h può avere. Il numero
massimo di nodi che un albero binario quasi completo di altezza h può avere è pari al numero di
nodi di albero binario completo di altezza h, ossia max = 2h+1 − 1 (vedi Proposizione 1.4). Ora
osserviamo che l’ albero binario quasi completo di altezza h con numero minimo di nodi ha la
seguente forma (dove Ts e Td sono degli alberi binari completi di altezza h − 2):

h­2 Ts Td h­2

Figure 4: Alberi binari quasi completo con minimo numero di nodi

Allora max = 1 + (#nodi (Ts ) + 1) + #nodi (Td ) = 2 + 2 · (2h−1 − 1) = 2h

2

Proposizione 1.7 L’altezza di un albero binario quasi completo T con n nodi è h = blog nc.

Dimostrazione: Per la Proposizione 1.6 abbiamo che 2h ≤ n ≤ 2h+1 − 1 < 2h+1 , cioè h ≤ log n <
h + 1 e, quindi, h ≤ blog nc < h + 1. Possiamo concludere che h = blog nc 2

La seguente proposizione fornisce un limite superiore al numero di nodi di ciascun sottoalbero

di un albero binario completo

3
Proposizione 1.8 Sia T un albero binario quasi completo con n nodi e siano Ts e Td il sottoalbero
sinistro e destro di T . Allora #nodi (Td ) ≤ #nodi (Ts ) < 2/3n.

Dimostrazione: Dalla definizione di albero binario quasi completo abbiamo che #nodi (Td ) ≤
#nodi (Ts ) (per definizione, infatti un albero binario quasi completo o è completo oppure mancano
delle foglie consecutive a partire dalla prima foglia a destra. Il primo sottoalbero “penalizzato”
dalla non completezza è il sottoalbero destro). Non ci resta che dimostrare che #nodi (Ts ) < 2/3n.
Analizziamo alcuni casi noti, a partire da quello descritto in Figura 5-(a) – albero binario completo
di altezza h. In questo caso #nodi (Ts ) è meno della metà del numero di nodi complessivo, infatti
n−1 n 2
#nodi (Ts ) = < < n
2 2 3
Cosa succede se aggiungiamo un’ulteriore nodo all’albero in Figura 5-(a) ottenendo cosı̀ l’albero in
Figura 5-(b)? In questo caso incrementiamo di una unità sia il numero di nodi complessivo che il
numero di nodi di Ts ed n = (2h+1 − 1) + 1 = 2h+1 e #nodi (Ts ) = (2h − 1) + 1 = 2h . Quindi:
n 2
#nodi (Ts ) = < n
2 3
In realtà, aggiungendo altri nodi nel sottoalbero sinistro il rapporto tra #nodi (Ts ) ed n continua
ad aumentare. Il caso peggiore si verfica quando aggiungiamo un altro livello completo di nodi al
sottoalbero sinistro ottenendo l’albero in Figura 5-(c). In questo caso #nodi (Ts ) = 2h+1 − 1 (Ts è
un albero completo di altezza h) ed n = 1 + #nodi (Ts ) + #nodi (Td ) = 1 + (2h+1 − 1) + (2h − 1) =
2h+1 + 2h − 1 = 2h · (2 + 1) − 1 = 3 · 2h − 1. Quindi:
2 2 2 2 2
#nodi (Ts ) = 2h+1 − 1 = 2 · 2h − 1 = (3 · 2h ) − 1 < (3 · 2h ) − = (3 · 2h − 1) = n
3 3 3 3 3
Osserviamo ora che aggingere uno o più nodi all’albero in Figura 5-(c) (ottenendo, ad esempio
l’albero in Figura 5-(d)) significa aumentare il numero di nodi complessivo, ma non il numero dei
nodi di Ts che rimane invariato (altri nodi possono essere aggiunti solo nel sottoalbero destro). In
altri termini, abbiamo che #nodi (Ts ) = 2h+1 − 1 ma n > 3 · 2h − 1 ≥ 3 · 2h . Allora:
2 2 2
#nodi (Ts ) = 2h+1 − 1 = 2 · 2h − 1 = (3 · 2h ) − 1 < (3 · 2h ) ≤ n
3 3 3
Se aggiungiamo tutti i nodi necessari a completare anche l’ultimo livello del sottoalbero destro,
otteniamo un albero della forma già descritta in Figura 5-(a), ossia un albero binario completo.
2

4
h­1 Ts Td h­1 h­1 Ts Td h­1

(a) (b)

h­1 Ts Td h­1 h­1 Ts Td h­1

(c) (d)

Figure 5: Numero di nodi di Ts