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).

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$ ).

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. Un MWS tree con $n$ entry ha $n + 1$ foglie.

Dimostrazione (induzione sull'altezza $h$ ). 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)

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)$ .

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$

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)$ .
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); si bilancia con nodi capienti, i (2,4).
MWS tree: albero ordinato, ogni nodo interno è un $d$ -nodo ( $d \ge 2$ ) con $d-1$ chiavi $k_1 < \dots < k_{d-1}$ e figli con $k_{i-1} < k < k_i$ ; foglie senza entry.
Ricerca MWTreeSearch: trova $i$ con $k_{i-1} < k \le k_i$ ; se $k = k_i$ trovato, altrimenti scende in $v_i$ ; $O(d_{max}\,h)$ .
Proposizione: MWS tree con $n$ entry ha $n+1$ foglie (induzione: $m = \sum(n_i + 1) = n + 1$ ).
(2,4): nodi con $2$ - $4$ figli + foglie tutte alla stessa profondità. Livello $i$ ha $2^i \le m_i \le 4^i$ nodi, $m_h = n+1$ $\Rightarrow$ $\frac12 \log_2(n+1) \le h \le \log_2(n+1)$ , $h = \Theta(\log n)$ .
Costi (2,4): get, put, remove $\Theta(\log n)$ (vedi Mappe e dizionari). Idea: inserimento con overflow (5-nodo) spezzato (terza chiave in su); rimozione con underflow, trasferimento o fusione (non richieste all'esame).
Confronto ABR / (2,4): $\Theta(h)$ contro $\Theta(\log n)$ ; dizionario remove(k,v): $\Theta(s + h)$ contro $\Theta(s + \log n)$ .
MWTreeSearch( $k$ , $v$ ): se $v$ esterno restituisce $v$ ; trova $i$ con $k_{i-1} < k \le k_i$ ; se $k = k_i$ restituisce $v$ , altrimenti ricorre su $v_i$ .
Esempio: radice $(10, 20)$ , figli $(3,7)$ , $(14,17)$ , $(25,30,35)$ : cercare $17$ ⇒ trovato nel secondo figlio; cercare $24$ ⇒ foglia (assente). Inserire $26$ : $(25,26,30,35)$ si spezza in $(25,26)$ e $(35)$ e $30$ sale nella radice.
Errori: dimenticare "foglie alla stessa profondità"; foglie contate come entry; cercare i figli come in un ABR.

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