Esercizio 18chiave negativa più grande in un albero (2,4)

Idea

Un (2,4) è un multi-way search tree con foglie tutte alla stessa profondità (vedi Multi-way search tree e alberi (2,4)Multi-way search tree (nodi con più entry, d figli e d-1 chiavi ordinate), ricerca in O(d_max h), un MWS tree con n entry ha n+1 foglie; albero (2,4): nodi con 2-4 figli e tutte le foglie alla stessa profondità, altezza Theta(log n) con dimostrazione, operazioni in Theta(log n); idea di overflow e underflow; tabella di confronto con gli alberi binari di ricerca.Multi-way search tree e alberi (2,4) →): in un nodo con chiavi $k_1 < \dots < k_{d-1}$ e figli $v_1, \dots, v_d$, le chiavi di $T_{v_i}$ stanno tra $k_{i-1}$ e $k_i$. Si cerca il predecessore di $0$ (la chiave più grande minore di $0$) con una discesa guidata dalla ricerca di $0$.

In un nodo $v$:

• sia $k_j$ la più grande chiave negativa tra quelle di $v$ (se esiste). Allora $k_j$ è un candidato, ed eventuali chiavi negative maggiori di $k_j$ possono stare solo in $T_{v_{j+1}}$, il sottoalbero tra $k_j$ e $k_{j+1}$ (le chiavi nei sottoalberi successivi sono $\ge k_{j+1} \ge 0$, quelle nei precedenti sono $< k_j$). Si aggiorna il candidato e si scende in $v_{j+1}$;
• se nessuna chiave di $v$ è negativa, tutte le chiavi sono $\ge 0$ e quelle negative possono stare solo nel primo sottoalbero (chiavi $< k_1$): si scende in $v_1$, senza toccare il candidato.

Si ripete fino a una foglia esterna; il candidato finale è la risposta (oppure "no negative key" se non è mai stato impostato).

(a) Pseudocodice

Algoritmo maxNegativeKey(T)
Input: (2,4)-tree T con chiavi intere distinte
Output: la più grande chiave negativa di T, oppure "no negative key"
cand <- null
v <- T.root()
while v non è una foglia do
    siano k1 < k2 < ... < k_{d-1} le chiavi di v e v1, ..., vd i figli
    j <- numero di chiavi negative di v          (le chiavi negative sono k1..kj, perché sono ordinate)
    if j >= 1 then cand <- k_j
    v <- v_{j+1}                                 (se j = 0: il primo figlio v_1)
if cand = null then return "no negative key"
else return cand

Le chiavi di un nodo sono ordinate, quindi le negative sono un prefisso $k_1, \dots, k_j$ e il confronto con $0$ si può fermare alla prima chiave non negativa: al più $3$ confronti per nodo.

Correttezza (invariante). All'inizio di ogni iterazione, se esiste una chiave negativa in $T$ più grande di cand (o qualunque chiave negativa, se cand è null), allora sta in $T_v$. Vale all'inizio ($v$ = radice, $T_v = T$). Nell'iterazione il candidato diventa la più grande chiave negativa di $v$ e si scende nell'unico sottoalbero che può contenerne di maggiori (ragionamento sopra), quindi l'invariante si conserva. Quando $v$ è una foglia esterna $T_v$ è vuoto, quindi cand è la più grande chiave negativa (o non ne esistono).

Esempio

Albero: radice con chiavi $(-5, 12)$; figli $(-20, -12)$, $(0, 5, 8)$ e $(30)$; sotto di essi solo foglie esterne.

• Radice: negative $-5$ ($j = 1$): cand $= -5$, si scende nel secondo figlio $(0, 5, 8)$ (chiavi tra $-5$ e $12$).
• Nodo $(0, 5, 8)$: nessuna negativa ($j = 0$): cand invariato, si scende nel primo figlio (foglia esterna): fine. Risultato: $-5$ ✓ (le chiavi $-20, -12$ sono minori).

Se invece il secondo figlio fosse $(-3, 5, 8)$: nel secondo nodo $j = 1$, cand $= -3$, si scende nel figlio tra $-3$ e $5$: foglia, risultato $-3$. Se tutte le chiavi sono $\ge 0$, cand rimane null e si restituisce "no negative key". (Verificato con 2000 (2,4)-tree casuali, confrontando con il massimo delle chiavi negative.)

(b) Complessità

Si visita un solo nodo per livello, dalla radice a una foglia esterna, quindi al più $h + 1$ nodi, con $h$ altezza. In un (2,4) ogni nodo ha al più $3$ chiavi, quindi il costo per nodo è $O(1)$. Poiché $h \in \Theta(\log n)$ (vedi la dimostrazione in Multi-way search tree e alberi (2,4)Multi-way search tree (nodi con più entry, d figli e d-1 chiavi ordinate), ricerca in O(d_max h), un MWS tree con n entry ha n+1 foglie; albero (2,4): nodi con 2-4 figli e tutte le foglie alla stessa profondità, altezza Theta(log n) con dimostrazione, operazioni in Theta(log n); idea di overflow e underflow; tabella di confronto con gli alberi binari di ricerca.Multi-way search tree e alberi (2,4) →), la complessità è

$$O(h) = O(\log n).$$

Anzi è sempre $\Theta(\log n)$: la discesa arriva comunque a una foglia esterna e tutte le foglie di un (2,4) sono alla stessa profondità $h$. È molto meglio dell'alternativa di visitare tutto l'albero, $\Theta(n)$.

Errori comuni

• Visitare tutto l'albero per cercare il massimo tra le chiavi negative: $\Theta(n)$ invece di $\Theta(\log n)$.
• Scendere nel figlio sbagliato: dopo aver trovato la chiave negativa più grande $k_j$ si scende in $v_{j+1}$ (a destra di $k_j$), non in $v_j$.
• Dimenticare di non cambiare il candidato quando un nodo non ha chiavi negative (ma di scendere comunque nel primo figlio).
• Non gestire il caso "nessuna chiave negativa".