Presentazione di PowerPoint

Rappresentazione di alberi
Lezione n°11
Prof.ssa Rossella Petreschi
Lezione del 7/11/2012 del Corso di Algoritmi e Strutture Dati
Riferimenti:
•Paragrafo 4,3 del testo Crescenzi, Gambosi,Grossi“Strutture di dati e algoritmi”
Edizioni: Addison Wesley
Numeri di Catalano
Il numero di alberi binari distinti con n nodi è pari al numero di Catalano
di dimensione n: Cn = (2n su n)/(n+1), risultato dell’equazione ricorsiva
Cn = ∑ Cs Cn-s-1, con 0 ≤ s ≤ n-1 e C0= C1=1
C2= 2
C3= 5
C4= 14
C5= 42
………….
Quanti bit per un albero binario?
Per rappresentare un qualunque albero binario con n nodi occorrono un numero
di bit pari a
log Cn= log[(2n su n)/ (n+1)] >
> log[(22n)/ (2n(n+1))] per la (*)
= 2n - O(logn)
(*) (2n su n) = (2n)!/n! (2n-n)! =
= (2n/2n) [2n (2n-1) (2n-2)…….1]/[n(n-1)(n-2)…1] [n(n-1)(n-2)…1]) =
= (1/2n)[(2n2n)/(nn)][(2n-1)(2n-2)/(n-1)(n-1)]… [3x2/1] >
> (1/2n)[(22n2/n2)][(2n-2)(2n-2)/(n-1)(n-1)]… [2x2/1] =
= (1/2n) [22n2/n2] [22(n-1)2 /(n-1)2]… [22/12] = (1/2n) x (22n)
Rappresentazione di un albero binario
Per ogni nodo u, ci soffermiamo su u-padre, u-fs e u-fd
Rappresentazione implicita: mantiene u-padre, ufs e ufd (ovvero le relazioni fra i
nodi) tramite una semplice regola matematica senza uso di memoria aggiuntiva (a
parte quella necessaria ai dati nei nodi, u-info).
Esempio: rappresentazione dell’heap
Utilizzabile solo per alcune classi di alberi binari
Oltre alla rappresentazione necessaria per u-info, usa un numero costante di
celle aggiuntive
Rappresentazione succinta:rappresentazione che impega una quantità di memoria
pari al minimo necessario, a parte termini additivi di ordine inferiore
Applicabile ad alberi binari qualunque
Oltre alla rappresentazione necessaria per u-info, usa strutture dati che
richiedono 2n+o(n)bit aggiuntivi differenziandosi fortemente dalla
rappresentazione esplicita che richiede 3nlogn bits aggiuntivi
Rappresentazione succinta per ampiezza
a
abcdef 1110100110000
b
c
d
e
nodo[0,…,n-1]
pieno[0,…,2n]
f
• Se
un nodo occupa la posizione i nell’array nodo, allora i bit corrispondenti ai
suoi due figli occupano le posizioni 2i+1 e 2i+2 nell’array pieno
• Se un nodo occupa la posizione i nell’array nodo, allora
pieno[2i+1]=1(pieno[ 2i+2]=1) iff il riferimento al fs (fd) non è null
Oltre all’array nodo, dobbiamo conteggiare 2n+1 bits necessari per l’array
pieno + lo spazio per navigare fra i due array
Come navigare: Rank,Select
abcdef
a
nodo[0,…,n-1]
b
1110100110000
pieno[0,…,2n];
c
d
e
• Rank(pieno,i): numero di 1 presenti nel segmento pieno[0,i]
0<=i<=2n
f
• Select(pieno,i): posizione dell’(i+1)-esimo 1 in pieno
0<=i<=Rank(pieno,2n)
Identificazione in nodo[] del fs(nodo[i]) o del fd(nodo[i]) :
f = 2i+1 (o d = 2i+2 ):posizione del fs (o fd) di i in pieno[];
Se pieno(f) non 0 (o pieno(d) non 0),
Rank(pieno,f (oppure d)): numero di 1 presenti nel segmento b[0,f]opure b[0,d];
nodo[Rank(pieno, f (oppure d)) -1]:fs[nodo(i)] oppure fd[nodo(i)].
Identificazione in nodo[] del padre(nodo[i]):
p = Select (pieno,i): bit 1 corrispondente a nodo[i] in pieno[];
nodo(p-1)/2: padre[nodo(i)].
Rappresentazione esplicita di Rank
Nella rappresentazione esplicita del rank si hanno m interi di logm bit ciascuno , da cui:
Spazio: mlogm bit; Tempo: O(1)
b(i) 1 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 ………
i
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ………
---------------------------------------------------------------------------------------Rank 1 2 3 3 4 4 4 5 6 6 6 6 6 6 6 6 ……….
Per ridurre lo spazio, si partiziona il vettore b in segmenti di dimensione k=logm/2 . Per ogni
segmento si calcola un solo valore di rango, quindi avremo m/k= m/(logm/2) interi di logm bits
ciascuno, da cui:
Spazio: mlogm bit;
Implementazione di Rank
Rank’
3
5
6
6
6
j
1
2
3
4
5
b(i)
1 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0……
i
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20……
---------------------------------------------------------------------------------------Rank 1 2 3 3 4 4 4 5 6 6 6 6 6 6 6 6 6 6 6 6 6…
Tempo O(1) per conoscere il Rank (=Rank’) degli elementi campionati e per gli altri???
per gli elementi non campionati…..
Rank(b,6) = Rank’[1] + #1nei primi 3 elementi di b[4,7] = 3 +1 =4
Numero degli 1 in un fissato intervallo di b
• C(h,2h): riporta il numero di 1 contenuti nelle prime h posizioni di tutti i possibili segmenti
elementari
• C(h,2h)= k2k = ((logm) /2)2(logm)/2 = O( m1/2 logm) elementi di O(logk) bit ciascuno
h=0
h=1
h=2
h=3
0000000011111111
0000111111112222
0011112211222233
0112122312232334
Rank(b,6) = Rank’[1] + #1nei primi 3 elementi di b[4,7] = Rank’[1] + C[2,9] = 3 +1 =4
Dove Rank’[1] è il valore del Rank campionato più vicino a sinistra all’indice di cui si vuole
calcolare il Rank; 9 è il numero decimale corrispondente al numero binario scritto in b nello
intervallo [4,7] e la riga 2 indica che si debbono contare gli 1 nei primi 3 elementi in [4,7].
In generale Rank(b,i) = Rank’ [q] + C[r,s]
dove q = ⎣i/k⎦ ed r = i-qk sono calcolabili in tempo O(1) e s???
Calcolo di s in O(1)
Rank’
j
b’(j)
3
1
14
5
2
9
6
3
8
6
4
0
6
5
0
m/k = 2m/logm
0≤ b’(j) < m1/2
b(i) 1 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0…… k=1/2 logm bit
i
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20……
---------------------------------------------------------------------------------------Rank 1 2 3 3 4 4 4 5 6 6 6 6 6 6 6 6 6 6 6 6 6…
Da cui
Rank(b,i) = Rank’ [q] + C[r,b’[q+1]]
Rank(b,6) = Rank’[1] + C[r,b’[q+1]] = Rank’[1] + C[2,b’[2]] = 3 +1 =4
2m è ancora troppo
Dato un array di 256 bits
i
32 interi di 8 bit ciascuno:
mlogm
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20……
b(i) 1 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0…
Rank 1 2 3 3 4 4 4 5 6 6 6 6 6 6 6 6 6 6 6 6 6
8 interi di 8 bit ciascuno:
2m (k=logm/2)
i
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20……
b(i) 1 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0…
Rank’
3
5
6
6
6
4 interi di 8 bit ciascuno:
O(m/logm)(k=(log2m)/8)
i
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20……
b(i)
1 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0…
Rank”
5
6
..di conseguenza
L’operazione di Rank(b,i) si esegue in tempo costante con l’aggiunta di o(m) bit ai bit richiesti dal
vettore b
Infatti:
Lo spazio occupato da Rank” è O(m/logm)bit
Lo spazio occupato da Rank’ è O(mloglogm/logm)bit
Si partiziona b in blocchi da k = (log2m)/8 bit e per ciascuno di questi blocchi si costruisce l’array
Rank’ relativo (così è garantito che ogni elemento di Rank’ richiede O(loglogm) bit dato che le
somme parziali all’interno di ogni singolo blocco Rank’ possono aver valore al più k)
Lo spazio occupato da C è O( m1/2 logm) O(log(logm/2)) bit
Quindi
• aggiungiamo o(m) ai bit richiesti da b’
• aggiungiamo Rank”(8i/log2m) al calcolo del Rank(b,i)
Esempio:
Rank(b,12) = Rank”(1) + Rank’(3) + C[0,b’[4]] = Rank”(1) + Rank’(3) + C[0,0] = 5 + 1 + 0 = 6
Alberi k-ari e ordinali
• alberi k-ari (o cardinali): ogni nodo ha k riferimenti ai figli, numerati
da 0 a k (binari se da 0 a 2)
• alberi ordinali: ogni nodo memorizza solamente la lista dei figli,
variabile da nodo a nodo.
Esiste la memorizzazione binarizzata che associa ad ogni albero ordinale
T un albero binario B costruito nel seguente modo:
r è la radice sia in T che in B.
Sia x un qualunque nodo in T non radice; in T, sia a il primo figlio a sx
di x (se esiste) e b il fratello più vicino a dx (se esiste).
In B, a e b saranno, rispettivamente, fs e fd di x.
Parentesi bilanciate
Un albero ordinale può essere codificato da una sequenza di parentesi bilanciate nella
seguente maniera: ogni nodo è codificato da una coppia di parentesi bilanciate e i suoi
figli sono ricorsivamente codificati ciascuno con una sequenza bilanciata di parentesi.
c
a
b
d
e
f
h
g
. a b dd b e gg e hh a cc ff .
( ( ( ( ) ) ( ( ) ) ( ) ) ( ) ( ))
Corrispondenza biunivoca
Esiste una corrispondenza biunivoca tra
•
Alberi binari (2-ari) di n nodi;
•
Alberi ordinali di n+1 nodi ;
•
Sequenze bilanciate di 2n parentesi
E la cardinalità di questi tre insiemi è il numero di catalano di dimensione n : C n = (2n su n)/(n+1)
a
c
a
b
c
d
e
g
b
f
d
e
f
h
g
h
. a b dd b e gg e hh a cc ff .
((( () )( () )())()())
NOTA:
non si possono rappresentare direttamente alberi binari mediante parentesi perché non c’è modo di distinguere fs da fd
La funzione Match
. a b dd b e gg e hh a ee ff .
( ( ( ( ) ) ( () ) () ) () () )
.abdeghcf
nodi
1 1 1 10 0 1 10 0 10 0 10 10 0
parentesi
Ovvero le parentesi aperte (chiuse) sono identificate con 1 (0)
Ogni nodo di indice i è posto in corrispondenza con l’indice della propria parentesi sinistra (left)
tramite le funzioni rank e select:
Rank (parentesi,l) = i
Select (parentesi,i) = l
Per individuare anche la parentesi destra (right), dobbiamo introdurre una nuova funzione Match
Match (parentesi,l) = r
Match (parentesi,r) = l
Rappresentazione succinta tramite parentesi bilanciate
tramite parentesi bilanciate si può, in tempo costante, con 2n +o(n) bit in totale, fornire
informazioni basiche sull’albero tipo:
•
calcolo della dimensione di un sottoalbero
Select (parentesi, i) = l
Match (parentesi, l) = r
size (i) = Rank(parentesi, r) - Rank(parentesi,l) + 1
Rappresentazione succinta fondamentale per rappresentare in forma compatta
alberi statici