Esercizi svolti a lezione il 9 Marzo 2001 & Esercizi proposti

(ATTENZIONE: chi trova un errore in questa pagina ricevera' un premio!!!)

Alberi binari (continua)

Lo scopo di questa lezione e' lo stesso della lezione precedente.

Gli esercizi presentati faranno riferimento alla UNIT "alberi" presentata nel corso di di Programmazione II.

Esercizi svolti a lezione

Stabilire se un albero binario e' completo

Un albero binario si dice completo se:

ogni nodo che NON e' una foglia ha esattamente 2 figli, e
tutte le foglie hanno lo stesso livello.

Sviluppiamo l'algoritmo procedendo come illustrato la scorsa lezione.

Intestazione

{AI: t e' inizializzato e "contiene" l'albero T}
{AF: restituisce true se T e' completo, false altrimenti}
function c (t:tree):boolean;

Algoritmo "ad alto livello"

Consideriamo la funzione "profondita' di un albero binario", con la seguente intestazione:

{AI: t e' inizializzato e "contiene" l'albero T}
{AF: restituisce la profondita' di T}
function p (t:tree):integer;

e la funzione "massimo di due interi", con la seguente intestazione:

{AI: a, b inizializzati}
{AF: restituisce il massimo tra a e b}
function max (a,b:integer):integer;

Possiamo ora scrivere l'algoritmo c:

c([]) = true
c([n,L,R]) = c(L) and c(R) and (p(L)=p(R))

e l'algoritmo p:

p([]) = 0
p([n,L,R]) = max(p(L),p(R))

Algoritmo in "pseudo-codice" Pascal
Passiamo immediatamente alla fase successiva.

Algoritmo in Pascal (CON I COMMENTI)

{AI: t e' inizializzato e "contiene" l'albero T}
{AF: restituisce la profondita' di T}
function p (t:tree):integer;
{SPECIFICA DELL'ALGORITMO:
 p([]) = 0
 p([n,L,R]) = max(p(L),p(R))
}
  begin
    if t=nil then p:=0
             else p:= 1+max(p(t^.left), p(t^.right));
      end;
  end;

Eventuali ottimizzazioni
PRIMA DI ESAMINARE IL CODICE Pascal, CHIDIAMOCI SE NON SIA POSSIBILE MIGLIORARE LA PROCEDURA INTERVENENDO SULLA SPECIFICA AD "alto livello". FORSE SIAMO PASSATI TROPPO PRESTO AL CODICE Pascal...

Esaminiamo l'algoritmo "ad alto livello" (Punto 2): dato un albero completo di m=2^h-1 nodi, dove h e' l'atezza dell'albero, ovvero il livello del nodo (foglia) di livello massimo +1 (associando livello 0 alla radice):

una chiamata della funzione c su di un tale albero comporta, contando anche la chiamata iniziale, 2^(h+1)-1 chiamate ricorsive (NOTA: la funzione e' chiamata anche sui figli vuoti delle foglie); 2^h-1 di tali chiamate corrispondono ai nodi dell'albero.
Per ogni livello k dell'albero (0<=k<=h-1) ci sono 2^k nodi di livello k.
Ciascuna chiamata della procedura c corrispondente ad un nodo dell'albero di livello k effettua due chiamate della procedura p su alberi completi di altezza h-(k+1).
Una chiamata della procedura p su di un albero completo di altezza q comporta 2^(q+1)-1 chiamate ricorsive della funzione stessa (contando anche la chiamata iniziale).

Il costo complessivo delle 2^h-1 chiamate delle funzione c corrispondenti ai nodi dell'albero e' quindi dato dalla formula (NOTAZIONE: +_{1<=j<=t} sta per "sommatoria per j da 1 a t):

+_{0<=k<=h-1} (2^k * 2 * (2^(h-(k+1)+1)-1))

+_{0<=k<=h-1} (2^(k+1) * (2^(h-k)-1))

+_{0<=k<=h-1} (2^(h+1)-2^(k+1))

h*2^(h+1) - (+_{0<=k<=h-1} 2^(k+1))

h*2^(h+1) - (2+2^2+2^3+...+2^h)

h*2^(h+1) - (2^(h+1)-2)

(h-1)*2^(h+1) +2

2 * ((h-1)*2^h + 1)

= (siccome 2^h - 1 = m)

2 * ( ((log (m-1))-1) * (m+1) + 1 )

Che e' un:

O ( m * (log m) )

La soluzione precedente ha quindi complessita' temporale O ( m * (log m) ), dove m e' il numero di nodi dell'albero completo in input. Ora presentiamo una nuova soluzione che ha complessita' temporale lineare in m.

L'intestazione e' sempre la stessa (la riportiamo per comodita'):

{AI: t e' inizializzato e "contiene" l'albero T}
{AF: restituisce true se T e' completo, false altrimenti}
function c (t:tree):boolean;

Algoritmo "ad alto livello"

Consideriamo una funzione "ausiliaria", con la seguente intestazione:

{AI: t e' inizializzato e "contiene" l'albero T}
{AF: restituisce la profondita' di T se T e' completo, 
     altrimenti restituisce -1}
function a (t:tree):integer;

Possiamo ora scrivere l'algoritmo c:

c(T) = (a(T) <> -1)

e l'algoritmo a:

a([]) = 0
a([n,L,R]) = sia l = a(L) r = a(R) 
             in 
             se (l=-1) allora -1
             altrimenti se (l<>r) allora -1
             altrimenti max(l,r)

Algoritmo in "pseudo-codice" Pascal
Passiamo immediatamente alla fase successiva.

Algoritmo in Pascal (CON I COMMENTI)

{AI: t e' inizializzato e "contiene" l'albero T}
{AF: restituisce la profondita' di T se T e' completo, 
     altrimenti restituisce -1}
function a (t:tree):integer;
{SPECIFICA DELL'ALGORITMO:
a([]) = 0
a([n,L,R]) = sia l = a(L) r = a(R) 
             in 
             se (l=-1) allora -1
             altrimenti se (l<>r) allora -1
             altrimenti 1+max(l,r)
}
  vat l,r:integer;
  begin
    if t=nil then a:=0
    else begin
           l:=a(t^.left);
           r:=a(t^.right);
           if l=-1 then a:=-1
           else if l<>r then a:=-1
           else a:= 1+max(l,r);
      end;
  end;

{AI: t e' inizializzato e "contiene" l'albero T}
{AF: restituisce true se T e' completo, false altrimenti}
function c (t:tree):boolean;
begin
  c := (a(t)<>-1)
end;

Sia m il numero di nodi dell'albero in input. Si osservi che

l'algoritmo ha complessita' temporale O(m), indipendentemente dalla forma dell'albero.
l'algoritmo ha complessita' spaziale O(h), dove h e' l'altezza dell'albero, ovvero: O(m) nel caso pessimo (quando l'albero e' degenere) e O(log m) nel caso medio.

Esercizi proposti

Un albero binario si dice bilanciato se:

per ogni nodo, le altezze dei sottoalberi destro e sinistro differiscono alpiu' di 1.

Un albero binario si dice quasi perfettamente bilanciato se:

e' ottenibile cancellando (simultaneamente) alcune foglie da un albero completo.

Esercizi

1. Realizzare una funzione che soddisfi la seguente specifica:

   {AI: t e' inizializzato e "contiene" l'albero T}
   {AF: restituisce true se T e' bilanciato, false altrimenti}
   function b (t:tree):boolean;

2. Realizzare una funzione che soddisfi la seguente specifica:

   {AI: t e' inizializzato e "contiene" l'albero T}
   {AF: restituisce true se T e' quasi perfettamente bilanciato, 
        false altrimenti}
   function q (t:tree):boolean;