Multi-way search tree e alberi (2,4)

In questa pagina 5

Problema degli ABR (vedi Alberi binari di ricerca): get, put, remove costano $\Theta(h)$ ma $h$ può essere proporzionale a $n$ . Due rimedi: ristrutturare l'albero quando lo sbilanciamento supera una soglia (AVL, alberi rosso-neri, non trattati) oppure rendere i nodi più capienti e usare la capienza per assorbire ingressi e uscite di entry: gli alberi (2,4). L'idea dei nodi capienti è la stessa dei B-tree usati nei database e nei file system: un nodo corrisponde a un blocco letto con un solo accesso a un disco (Memoria esterna - dischi, RAID e memorie ottiche, Gerarchia di memoria e principio di località), quindi conviene avere pochi livelli e molte chiavi per nodo.

Multi-way search tree

Definizione (multi-way search tree). Un multi-way search tree (MWS tree) è un albero ordinato (vedi Alberi) in cui:

ogni nodo interno ha $\ge 2$ figli;

ogni nodo interno con $d \ge 2$ figli $v_1, \dots, v_d$ ( $d$ -nodo) memorizza $d - 1$ entry $(k_1, x_1), \dots, (k_{d-1}, x_{d-1})$ con $k_1 < k_2 < \dots < k_{d-1}$ ;

per $1 \le i \le d$ ogni chiave $k$ del sottoalbero $T_{v_i}$ soddisfa $k_{i-1} < k < k_i$ (con $k_0 = -\infty$ , $k_d = +\infty$ ).

Esempio. Un $3$ -nodo con chiavi $10<20$ ha $3$ figli, con chiavi $<10$ , in $(10,20)$ e $>20$ . Il caso $d=2$ è il nodo dell'ABR (Alberi binari di ricerca): una chiave e due sottoalberi, uno con chiavi minori e uno con chiavi maggiori. Gli intervalli aperti $(k_{i-1},k_i)$ sono quelli dei intervalli di numeri reali: gli $d$ intervalli $(-\infty,k_1),(k_1,k_2),\dots,(k_{d-1},+\infty)$ coprono tutta la retta tranne le chiavi del nodo, quindi ogni chiave cercata ha esattamente un posto dove andare.

Per convenzione, come negli ABR, le foglie non memorizzano entry. Un ABR è il caso in cui ogni nodo interno è un 2-nodo.

Esempio di 4-nodo: tre chiavi $k_1 < k_2 < k_3$ e quattro figli, con chiavi $< k_1$ in $v_1$ , in $(k_1, k_2)$ in $v_2$ , in $(k_2, k_3)$ in $v_3$ , $> k_3$ in $v_4$ .

Ricerca

Algoritmo MWTreeSearch(k, v)
Input: chiave k, nodo v     Output: nodo di T_v con la chiave k, o la foglia "giusta" per k
if T.isExternal(v) then return v
siano (k1,x1), ..., (k_{d-1}, x_{d-1}) le entry di v
trova i con k_{i-1} < k <= k_i   (k_0 = -infinito, k_d = +infinito)
if k = k_i then return v
else return MWTreeSearch(k, v_i)

get(k): cerca come sopra; se il risultato è una foglia restituisce null, altrimenti la entry in $v$ con chiave $k$ . Complessità: il cammino ha lunghezza $\le h$ e in ogni nodo si cerca tra $\le d_{max}$ chiavi (se le entry di un nodo sono in una mappa secondaria, ad esempio una lista): $O(d_{max} \, h)$ .

Esempio: radice $(10, 20)$ con figli $(3, 7)$ , $(14, 17)$ , $(25, 30, 35)$ . Cercare $17$ : tra $10$ e $20$ si va nel secondo figlio $(14, 17)$ e si trova. Cercare $24$ : $24 > 20$ , si scende nel terzo figlio; $24 < 25$ , si scende nel suo primo figlio, che è una foglia: assente.

Numero di foglie

Proposizione (numero di foglie di un MWS tree). Un MWS tree con $n$ entry ha $n + 1$ foglie.

Esempio. Con radice $(10,20)$ e figli $(3,7)$ , $(14,17)$ , $(25,30,35)$ le entry sono $9$ e le foglie $3+3+4=10=9+1$ .

Dimostrazione (induzione sull'altezza $h$ , vedi Principio di induzione). Base $h = 0$ : la sola radice è una foglia, $n = 0$ , $1$ foglia. Passo: $T$ di altezza $h+1$ con radice $d$ -nodo, sottoalberi $T_1, \dots, T_d$ con $n_i$ entry e $m_i$ foglie, altezze $\le h$ . Per ipotesi $m_i = n_i + 1$ . Allora $n = (d-1) + \sum n_i$ e $m = \sum m_i = \sum (n_i + 1) = d + \sum n_i = 1 + (d - 1) + \sum n_i = n + 1$ . $\square$

(Se tutti i nodi interni fossero $d$ -nodi, l'albero sarebbe $d$ -ario e le foglie sarebbero $(d-1) \cdot (\text{nodi interni}) + 1$ , con $(d-1) \cdot (\text{nodi interni}) =$ numero di entry.)

Alberi (2,4)

Definizione (albero (2,4) e altezza). Un albero (2,4) è un MWS tree tale che:

ogni nodo interno è un $d$ -nodo con $2 \le d \le 4$ (cioè ha $1$ , $2$ o $3$ entry);

tutte le foglie hanno la stessa profondità.

Proposizione. Un (2,4) con $n > 0$ entry ha altezza $\Theta(\log n)$ .

Esempio. Con $n=1000$ entry l'altezza è tra $\log_4 1001\approx5$ e $\log_2 1001\approx10$ , cioè $\Theta(\log n)$ .

Dimostrazione. Sia $h$ l'altezza (= livello delle foglie) e $m_i$ il numero di nodi al livello $i$ . Si ha $m_0 = 1$ e, poiché ogni nodo interno ha tra $2$ e $4$ figli e le foglie sono tutte a livello $h$ , $2^i \le m_i \le 4^i$ . In particolare $2^h \le m_h \le 4^h$ . Ma $m_h = n + 1$ (proposizione sulle foglie). Quindi $n + 1 \ge 2^h \Rightarrow h \le \log_2(n+1)$ e $n + 1 \le 4^h \Rightarrow h \ge \frac12 \log_2(n+1)$ . Dunque $h \in \Theta(\log n)$ . $\square$

I passaggi sui logaritmi: $n+1 \ge 2^h$ si inverte applicando $\log_2$ , funzione crescente (Esponenziale e logaritmo), e dà $h \le \log_2(n+1)$ ; $n+1 \le 4^h = 2^{2h}$ dà $\log_2(n+1) \le 2h$ , cioè $h \ge \frac12\log_2(n+1)$ . Il grafico mostra la fascia in cui sta l'altezza di un (2,4) con $n$ entry: per $n=1000$ è tra $\approx5$ e $\approx10$ , mentre un ABR degenere avrebbe altezza $999$ .

Grafico interattivo: Altezza di un albero (2,4) con n entry: compresa tra metà di log2(n+1) (tutti 4-nodi) e log2(n+1) (tutti 2-nodi); per n = 1000 tra 5 e 10

Controllo sull'esempio della ricerca (radice $(10,20)$ con tre figli): $n=9$ , altezza $2$ ; le foglie sono $10=n+1$ e valgono $2^2=4\le10\le4^2=16$ .

Corollario. In un (2,4) con $n$ entry MWTreeSearch e get costano $\Theta(\log n)$ (ogni nodo ha $\le 3$ chiavi, $d_{max}$ è costante). Anche put e remove si implementano in $\Theta(\log n)$ ; la loro implementazione non è richiesta all'esame ma l'idea è semplice:

Inserimento: si cerca la foglia $w$ e si inserisce la chiave nel nodo $v$ padre di $w$ . Se $v$ diventa un 5-nodo (4 chiavi, overflow) lo si spezza: la terza delle quattro chiavi sale al padre, le prime due restano in un nodo (a $3$ figli) e l'ultima forma l'altro (a $2$ figli). L'overflow può propagarsi verso la radice; se la radice si spezza, nasce una nuova radice e l'altezza cresce di $1$ (tutte le foglie scendono insieme: la condizione 2 resta vera). Esempio: inserendo $26$ nel nodo $(25, 30, 35)$ si ha $(25, 26, 30, 35)$ : si spezza in $(25, 26)$ e $(35)$ e $30$ sale nella radice, che diventa $(10, 20, 30)$ .

Perché la condizione 2 resta vera: lo spezzamento non cambia la profondità delle foglie (i nuovi nodi sono allo stesso livello del vecchio) e la salita della chiave aumenta di $1$ i figli del padre senza cambiare livelli. Inoltre i due nodi nati dallo spezzamento hanno $3$ e $2$ figli, quindi rispettano il vincolo $2\le d\le4$ . Sequenza completa di inserimenti $10,20,30,40,50,60,70$ partendo dall'albero vuoto (una sola foglia):

inserimento	albero dopo	note
$10$	$(10)$	la foglia diventa nodo interno con due foglie
$20$	$(10,20)$	3-nodo
$30$	$(10,20,30)$	4-nodo, ancora valido
$40$	$(10,20,30,40)$ $\to$ radice $(30)$ con figli $(10,20)$ e $(40)$	overflow: la terza chiave sale e crea una nuova radice, altezza $1\to2$
$50$	radice $(30)$ , figli $(10,20)$ e $(40,50)$	$50>30$ , si va a destra
$60$	radice $(30)$ , figli $(10,20)$ e $(40,50,60)$
$70$	$(40,50,60,70)$ $\to$ radice $(30,60)$ , figli $(10,20)$ , $(40,50)$ , $(70)$	overflow: sale $60$ nella radice

In ogni istante le foglie sono tutte alla stessa profondità, e l'altezza è passata da $1$ a $2$ solo quando si è spezzata la radice.

Rimozione: una entry di un nodo non terminale si sostituisce con il predecessore inorder, poi si toglie la entry da un nodo con foglie come figli. Se il nodo rimane senza entry (underflow) si fa un trasferimento da un fratello con almeno $3$ figli oppure una fusione con un fratello a $2$ figli (che può propagare l'underflow in su; se la radice si svuota, l'altezza diminuisce).

Dizionario con alberi di ricerca

Un dizionario (multimap, vedi Mappe e dizionari) si realizza o con una mappa di coppie $(k, L_k)$ , o modificando ABR e (2,4) per ammettere chiavi uguali.

Confronto

Metodo	ABR	(2,4)
`get(k)`	$\Theta(h)$	$\Theta(\log n)$
`put(k, v)`	$\Theta(h)$	$\Theta(\log n)$
`remove(k)`	$\Theta(h)$	$\Theta(\log n)$
`remove(k, v)` (dizionario)	$\Theta(s + h)$	$\Theta(s + \log n)$

( $s$ = numero di valori associati alla chiave.) Nell'ABR $h$ può essere $n - 1$ ; nel (2,4) il bilanciamento è garantito dalla struttura.

Errori comuni

Dimenticare la condizione "tutte le foglie alla stessa profondità": senza di essa l'altezza non è logaritmica.
Contare le foglie come entry: un MWS tree con $n$ entry ha $n+1$ foglie vuote.
Cercare linearmente i figli come in un ABR: in un $d$ -nodo si cerca l'intervallo $k_{i-1} < k \le k_i$ tra $d - 1$ chiavi.
Stimare la complessità come $\Theta(h)$ senza specificare $h = \Theta(\log n)$ per i (2,4).

Versione ripasso

Perché: negli ABR $h$ può essere $\Theta(n)$ (vedi Alberi binari di ricerca). I nodi capienti degli alberi (2,4) tengono l'altezza logaritmica; sono l'idea dei B-tree dei database e dei file system, dove un nodo è un blocco di disco (Gerarchia di memoria e principio di località).
MWS tree: albero ordinato in cui ogni nodo interno con $d\ge2$ figli è un $d$ -nodo con $d-1$ entry $k_1<\dots<k_{d-1}$ ; il figlio $v_i$ contiene chiavi $k$ con $k_{i-1}<k<k_i$ (con $k_0=-\infty$ , $k_d=+\infty$ ). Le foglie non memorizzano entry. Un ABR è il caso in cui tutti i nodi interni sono 2-nodi.
Ricerca MWTreeSearch(k, v): se $v$ è esterno restituisce $v$ ; altrimenti trova $i$ con $k_{i-1}<k\le k_i$ ; se $k=k_i$ restituisce $v$ , altrimenti ricorre su $v_i$ . Costo $O(d_{max}\,h)$ .
Esempio: radice $(10,20)$ con figli $(3,7)$ , $(14,17)$ , $(25,30,35)$ . Cercare $17$ dà il nodo $(14,17)$ ; cercare $24$ arriva in una foglia: assente.
Proposizione: un MWS tree con $n$ entry ha $n+1$ foglie. Induzione sull'altezza: se il sottoalbero $i$ ha $n_i$ entry e $m_i=n_i+1$ foglie, la radice con $d$ figli ha $m=\sum(n_i+1)=d+\sum n_i=n+1$ . Nell'esempio: $3+3+4=10=9+1$ .
Alberi (2,4): MWS tree con nodi di $2$ , $3$ o $4$ figli (da $1$ a $3$ entry) e tutte le foglie alla stessa profondità. Al livello $i$ ci sono $2^i\le m_i\le 4^i$ nodi e $m_h=n+1$ , quindi $\frac12\log_2(n+1)\le h\le\log_2(n+1)$ : $h=\Theta(\log n)$ .
Costi: get, put, remove in $\Theta(\log n)$ (vedi Mappe e dizionari). Inserimento: se un nodo diventa un 5-nodo (overflow) si spezza, la terza chiave sale al padre e, se arriva alla radice, l'altezza cresce di $1$ . Esempio: inserire $26$ in $(25,30,35)$ dà $(25,26,30,35)$ , spezzato in $(25,26)$ e $(35)$ , con $30$ che sale nella radice. La rimozione con underflow (trasferimento o fusione) non è richiesta all'esame.
Confronto: ABR $\Theta(h)$ , (2,4) $\Theta(\log n)$ per get, put e remove. Per il dizionario, remove(k,v) costa $\Theta(s+h)$ contro $\Theta(s+\log n)$ , con $s$ valori associati alla chiave.
Inserimento senza overflow: se la foglia ha meno di $3$ entry, la chiave si aggiunge e basta; nessuna foglia cambia profondità.
Sequenza: inserendo $10,20,30,40$ si ottiene la radice $(30)$ con figli $(10,20)$ e $(40)$ : l'altezza passa da $1$ a $2$ solo quando si spezza la radice.
Errori tipici: dimenticare "foglie alla stessa profondità"; contare le foglie come entry (sono $n+1$ foglie vuote); cercare i figli come in un ABR invece che nell'intervallo $k_{i-1}<k\le k_i$ .

Multi-way search tree e alberi (2,4)