Descriviamo ora una struttura utile per implementare, con buona efficienza nel caso medio, programmi astratti sulla struttura dati PARTI DI A ORDINATO. I sottoinsiemi di A vengono qui rappresentati medi-ante alberi di ricerca binaria. Le operazioni che dobbiamo implementare sono quelle di MIN, MEMBER, INSERT e DELETE.
Ricordiamo innanzitutto che A `e un insieme totalmente ordinato e denotiamo con ≤ la relativa re-lazione d’ordine. Dato un sottoinsieme S ⊆ A, un albero di ricerca binaria per S `e un albero binario T , i cui vertici sono etichettati da elementi di S, che gode delle seguenti propriet`a . Denotando con E(v) l’etichetta di ogni vertice v, abbiamo:
2. per ogni vertice v, se u `e un vertice del sottoalbero sinistro di v allora E(u) < E(v); 3. per ogni vertice v, se u `e un vertice del sottoalbero destro di v allora E(u) > E(v).
Dato S = {s1, s2, . . . , sn}, ordinando i suoi elementi in ordine crescente otteniamo un vettore S = (S[1], S[2], . . . , S[n]); `e facile dimostrare per induzione che un albero binario T di n nodi diventa un albero di ricerca binaria per S se, per ogni k = 1, 2, . . . , n, si etichetta con S[k] il k-esimo vertice visitato durante l’attraversamento in ordine simmetrico di T .
Per esempio, sia A l’insieme delle parole della lingua italiana ordinate in modo lessicografico e sia S l’insieme { la, pecora, `e , un, animale, feroce }; tale insieme `e rappresentato dal vettore ( animale, `e
, feroce, la, pecora, un ). Nel seguente albero binario di 6 nodi i vertici sono numerati secondo l’ordine
simmetrico: 1 @ @ 3 2 4 H H H H H 5 @ @ 6
Il seguente risulta allora un albero di ricerca binaria per S:
1 animale @ @ 3 feroce 2 `e 4 la H H H H H 5 pecora @ @ 6 un
Possiamo rappresentare un albero di ricerca binaria mediante le tabelle sin, des, E e padre. Nel nostro caso otteniamo la seguente rappresentazione:
vertici sin des E padre
1 0 3 animale 4 2 0 0 e’ 3 3 2 0 feroce 1 4 1 5 la 0 5 0 6 pecora 4 6 0 0 un 5 `
E chiaro che, per ogni nodo v di T , i nodi con etichetta minore di E(v) si trovano eventualmente nel sottoalbero sinistro di v. Quindi, possiamo determinare il vertice con etichetta minima semplicemente scorrendo il ramo sinistro dell’albero. Il procedimento `e descritto dalla seguente procedura nella quale rappresentiamo con r la radice dell’albero.
ProcedureMIN(r)
begin
v := r
whilesin(v) 6= 0dov := sin(v)
returnv
end
Analogamente, l’operazione MEMBER(x, S) pu`o essere eseguita mediante la seguente procedura ri-corsiva CERCA(x, v) che verifica se nel sottoalbero avente per radice v esiste un nodo di etichetta x.
ProcedureCERCA(x, v)
begin
ifx := E(v)then returnvero
ifx < E(v) then ifsin(v) 6= 0then returnCERCA(x, sin(v))
else returnf also
ifx > E(v) then ifdes(v) 6= 0then returnCERCA(x, des(v))
else returnf also
end
L’appartenenza di un elemento all’insieme S rappresentato dall’albero di ricerca binaria T pu`o essere allora verificata semplicemente mediante la chiamata CERCA(x, r).
Per quanto riguarda l’operazione INSERT(x, S), osserviamo che se x appartiene a S l’insieme non viene modificato. Se invece S `e rappresentato dall’albero di ricerca binaria T e x 6∈ S, l’algoritmo deve inserire in T un nuovo nodo etichettato con x, preservando la struttura di albero di ricerca binaria. In questo modo l’algoritmo restituisce un albero di ricerca binaria per l’insieme S ∪ {x}. Il procedimento `e ottenuto mediante la seguente procedura ricorsiva che eventualmente inserisce un nodo etichettato x nel sottoalbero di radice v.
ProcedureINSERT(x, v)
begin
ifx < E(v)then ifsin(v) 6= 0thenINSERT(x, sin(v))
elseCREA NODO SIN(v, x)
ifx > E(v)then ifdes(v) 6= 0thenINSERT(x, des(v))
elseCREA NODO DES(v, x)
end
Qui la procedura CREA NODO SIN(v, x) introduce un nuovo nodo ˆv, figlio sinistro di v ed etichettato con x, aggiornando la tabella come segue:
sin(v) := ˆv; padre(ˆv) := v; E(ˆv) := x; sin(ˆv) := 0; des(ˆv) := 0 La procedura CREA NODO DES(v, x) `e definita in maniera analoga.
Osserviamo che l’implementazione delle operazioni MIN, DELETE e INSERT non richiedono l’u-so della tabella padre(v); tale tabella risulta invece indispensabile per una efficiente implementazione dell’operazione DELETE.
Una possibile implementazione di DELETE(x, S), dove S `e rappresentato da un albero di ricerca binaria T , richiede l’esecuzione dei seguenti passi:
1. Determina l’eventuale nodo v tale che x = E(v). 2. Se v possiede al pi`u un figlio, allora:
a) se v `e una foglia basta togliere v dall’albero, ovvero eliminare la riga corrispondente nella
tabella aggiornando opportunamente quella relativa al padre;
b) se v `e radice e ha un unico figlio ˆv basta ancora togliere v dall’albero e assegnare 0 a padre(ˆv) rendendo cos`ı ˆv radice dell’albero;
c) se v non `e radice e ha un unico figlio ˆv basta togliere v dall’albero collegando direttamente ˆv con padre(v). Naturalmente se v era figlio sinistro si pone sin(padre(v)) := ˆv, mentre se v era figlio destro si pone des(padre(v)) := ˆv.
Nel seguito indichiamo con TOGLI(v) la procedura che esegue i calcoli relativi al punto 2. `E chiaro che se v possiede al pi`u un figlio l’esecuzione di TOGLI(v) permette di ottenere un albero di ricerca binaria per S − {x}.
3. Se v ha due figli si pu`o determinare il vertice vM che ha etichetta massima nel sottoalbero di sinistra di v. Poich´e vM non ha figlio destro, associando a v l’etichetta di vM e applicando la procedura TOGLI(vM) si ottiene un albero di ricerca per S − {x}.
Il passo 3) richiede il calcolo del vertice di etichetta massima nel sottoalbero che ha per radice un nodo qualsiasi u. Questo pu`o essere determinato scorrendo il ramo di destra dell’albero, come descritto nella seguente procedura.
ProcedureMAX(u)
begin
v := u
whiledes(u) 6= 0dov := des(v)
returnv
end
La procedura principale per l’implementazione dell’operazione DELETE `e allora la seguente:
ProcedureELIMINA(x, v)
begin
ifx < E(v) ∧ sin(v) 6= 0thenELIMINA(x, sin(v))
ifx > E(v) ∧ des(v) 6= 0thenELIMINA(x, des(v))
ifx = E(v) then ifv ha al piu’ un figliothenTOGLI(v)
else begin vM := MAX(sin(v)) E(v) := E(vM) TOGLI(vM) end end
L’operazione DELETE(x, S), dove S `e un insieme rappresentato da un albero di ricerca binaria T , con radice r, pu`o quindi essere implementata dalla semplice chiamata ELIMINA(x, r), dove r `e la radice di T .
Le procedure qui delineate MEMBER, INSERT, MIN, e DELETE richiedono, se applicate a un albero di altezza h, un tempo di calcolo O(h); ricordiamo che un albero binario di n nodi ha un’altezza h tale che log n ≤ h ≤ n − 1. Poich´e applicando all’insieme vuoto un programma astratto di n operazioni MEMBER, INSERT, MIN e DELETE si ottengono alberi di al pi`u n elementi, ne segue che l’esecuzione di un tale programma richiede tempo O(n2). Purtroppo questo limite superiore `e stretto: se infatti, in un albero di ricerca binaria inizialmente vuoto, inseriamo consecutivamente n elementi a1, a2, . . . , antali che a1 < a2 < · · · < an, si eseguonoPn−1
k=0k ∼ n22 operazioni di confronto.
Fortunatamente le prestazioni nel caso medio risultano migliori. Consideriamo infatti n elementi a1, a2, . . . , antali che a1< a2 < · · · < ane supponiamo di voler inserire tali elementi in un ordine qual-siasi nell’ipotesi che tutti i possibili ordinamenti siano equiprobabili. Pi`u precisamente scegliamo una permutazione casuale (ap(1), ap(2), . . . , ap(n)) degli n elementi assumendo che tutte le n! permutazioni abbiano la stessa probabilit`a di essere scelte. Consideriamo quindi il programma INSERT(ap(1), S), INSERT(ap(2), S), . . . , INSERT(ap(n), S) e denotiamo con Tnil numero medio di confronti necessari per eseguire tale programma. Osserviamo innanzitutto che, per ogni k ∈ {1, 2, . . . , n}, ap(1) = ak con probabilit`a 1/n. In questo caso l’albero di ricerca ottenuto alla fine dell’esecuzione dell’algoritmo avr`a la radice etichettata da ak, mentre il sottoalbero di sinistra della radice conterr`a k − 1 elementi e quello di destra n − k. Questo significa che durante la costruzione dell’albero, il valore ap(1)sar`a confrontato con tutti gli altri elementi della sequenza, per un totale di n − 1 confronti; inoltre, eseguiremo in media Tk−1
confronti per costruire il sottoalbero di sinistra e Tn−k per costruire quello di destra. Di conseguenza, nel caso ap(1) = ak, si eseguono n − 1 + Tk−1+ Tn−kconfronti. Poich´e questo evento si verifica con probabilt`a 1/n per ogni k, otteniamo la seguente equazione, valida per ciascun n > 1:
Tn= n X k=1 1 n(n − 1 + Tk−1+ Tn−k). Mediante semplici passaggi questa equazione si riduce alla ricorrenza
Tn= (
0 se n = 1
Pn
k=1 1n(n − 1 + Tk−1+ Tn−k) altrimenti
che coincide con quella ottenuta nell’analisi di Quicksort, studiata nelle sezioni 6.6.1 e 7.4.2. Si ottiene in questo modo il valore Tn= 2n log n + O(n).
Possiamo allora concludere affermando che, nel caso medio, n operazioni MEMBER, INSERT e MIN eseguite su un albero di ricerca binaria inizialmente vuoto, richiedono O(n log n) passi.
Esercizi
1) Le procedure CERCA, INSERT e ELIMINA appena descritte sono procedure risorsive. Quali di queste forniscono un esempio di ricorsione terminale?
2) Descrivere una versione iterativa delle procedure CERCA, INSERT e ELIMINA.
3) Descrivere un algoritmo per ordinare un insieme di elementi S assumendo in input un albero di ricerca binaria per S. Mostrare che, se S possiede n elementi, l’algoritmo funziona in tempo Θ(n) (si assuma il criterio uniforme).
4) Usando gli alberi di ricerca binaria (e in particolare la procedura di inserimento) si descriva un algoritmo di ordinamento generico. Svolgere l’analisi dell’algoritmo nel caso peggiore e in quello medio (nelle solite ipotesi di equidistribuzione) e confrontare i risultati con quelli relativi a Quicksort.