alberi binari: proprietà matematiche (1)

un albero binario completo con N vertici interni ha N+1 foglie

per induzione sull'altezza dell'albero: la proprietà vale per l'albero di un solo vertice, e per alberi con più vertici vale sui sottoalberi della radice per ipotesi d'induzione

un albero binario completo con N vertici interni ha 2N archi: N-1 fra vertici interni e N+1 archi a foglie

segue dalla proprietà precedente e dall'unicità dell'arco fra ogni vertice (non radice) e il padre

definizioni:

livello di un vertice in un albero: numero di vertici che lo precedono nel cammino dalla radice
altezza di un albero: massimo dei livelli dei suoi vertici
lunghezza del cammino di un albero: somma dei livelli dei suoi vertici
lunghezza del cammino interno di un albero: somma dei livelli dei suoi vertici interni
lunghezza del cammino esterno di un albero: somma dei livelli delle sue foglie

in un albero binario completo con N vertici interni, se I è la lunghezza del cammino interno ed E è la lunghezza del cammino esterno, allora E = I + 2N

qualsiasi albero binario completo con N vertici può essere costruito partendo dall'albero che consta della sola radice e iterando quindi N volte il rimpiazzamento di una foglia con un vertice interno padre di due foglie: se k è il livello di una foglia rimpiazzata, la lunghezza del cammino interno aumenta di k mentre quella del cammino esterno aumenta di k+2 (due nuove foglie di livello k+1 meno una di livello k)

alberi binari: proprietà matematiche (2)

l'altezza h di un albero binario completo con N vertici interni soddisfa: ⌊lg N⌋+1 ≤ h ≤ N-1

il limite inferiore si ha con alberi bilanciati (v. esercizio 1)
- cioè alberi binari in cui le altezze dei due sottoalberi di qualsiasi vertice interno differiscono di 1 al più
quello superiore quando i vertici interni formano una catena

la lunghezza del cammino interno, I, di un albero binario completo con N vertici interni soddisfa: N lg(N/4) < I ≤ N(N-1)/2

i limiti inferiore e superiore si hanno con gli stessi alberi di cui sopra
- per il limite inferiore, si noti che un albero completo bilanciato ha N+1 foglie di livello almeno ⌊lg N⌋, di cui almeno due di livello ⌊lg N⌋+1: moltiplicando e applicando l'ultima proprietà dalla pagina precedente si ha
  I = E-2N > (N+1)⌊lg N⌋-2N > N lg(N/4) (v. esercizio 2)

gli alberi bilanciati sono spesso utili al progetto di algoritmi ottimali

attraversamento ricorsivo di alberi

attraversamento di un albero: visita (l'informazione associata a) tutti i vertici dell'albero

per gli alberi binari, si hanno tre discipline di visita ricorsiva, cioè basate sulla struttura ricorsiva dell'albero:

preordine: visita prima il vertice, poi i sottoalberi di sinistra e destra
inordine: visita il sottoalbero di sinistra, poi il vertice, poi il sottoalbero di destra
- l'ordine di visita dei sottoalberi può essere scambiato
postordine: visita prima i sottoalberi di sinistra e destra, poi il vertice

definizione ricorsiva di funzione di attraversamento in preordine (btree* = btlink):

void attraversa(btlink h, void visita(btlink))
{ if (h == 0) return; 
  visita(h); attraversa(h->l, visita); attraversa(h->r, visita); }

per ottenere da questa le analoghe definizioni per le altre due discipline ricorsive di attraversamento basta spostare opportunamente l'invocazione di visita(h)

attraversamento preordine non ricorsivo

le tre discipline di visita ricorsiva di alberi binari danno soluzioni a svariati problemi

ad es., fra quelli visti, l'algoritmo ricorsivo per il problema delle torri di Hanoi sfrutta la visita inordine, mentre per il problema del righello le tre discipline di visita corrispondono tutte a soluzioni, diverse per l'ordine di tracciamento

le suddette discipline di visita possono essere realizzate anche con algoritmi non ricorsivi, impiegando una pila

ecco ad esempio un algoritmo non ricorsivo per l'attraversamento preordine
- l'ordine delle push dei sottoalberi nella pila è l'inverso di quello della loro visita

void attraversa(btlink h, void visita(btlink))
{ Stack<btlink> s(max);
  s.push(h);
  while (!s.empty())
  { visita(h = s.pop());
    if (h->r != 0) s.push(h->r);
    if (h->l != 0) s.push(h->l);
} }

attraversamento per livelli non ricorsivo

nessuna delle tre suddette discipline di visita è adeguata al caso in cui si voglia attraversare un albero binario facendo procedere assieme gli attraversamenti dei suoi sottoalberi

si può adoperare in tal caso l'attraversamento per livelli, che consiste nel visitare tutti i vertici di ciascun livello prima di passare a quelli del livello successivo

è notevole il fatto che un algoritmo a tal scopo si può ottenere da quello non ricorsivo di attraversamento preordine, semplicemente adoperando una coda in luogo della pila, con le corrispondenti operazioni di inserimento e rimozione, dove l'ordine degli inserimenti coincide stavolta con quello della successiva visita, per via della disciplina FIFO

void attraversa(btlink h, void visita(btlink))
{ Queue<btlink> q(max);
  q.put(h);
  while (!q.empty())
  { visita(h = q.get());
    if (h->l != 0) s.put(h->l);
    if (h->r != 0) s.put(h->r);
} }

esercizi

dimostrare che, un po' diversamente dall'enunciato della Proprietà 5.8 nel testo (Sedgewick, 2003), a p. 243, l'altezza di un albero binario completo bilanciato di N vertici interni è almeno ⌊lg N⌋+1
dimostrare che la lunghezza del cammino interno di un albero binario completo bilanciato di N vertici interni è maggiore di N lg(N/4)
definire una funzione non ricorsiva per l'attraversamento postordine di un albero binario, adoperando una pila
definire una funzione non ricorsiva per l'attraversamento inordine di un albero binario, adoperando una pila
esercizio 5.81 del testo (Sedgewick, 2003), p.250: mostrare che, se una foresta è rappresentata da un albero binario secondo la corrispondenza biunivoca indicata nella lezione precedente, l'attraversamento preordine della foresta si realizza con l'attraversamento preordine dell'albero binario, mentre quello postordine della foresta si realizza con quello inordine dell'albero binario

Alberi binari, attraversamento di alberi

Lezione 22 di Programmazione 2

Indice