Esercizio 17terremoto forte recente in un albero di ricerca

(a) Idea

Si cerca una entry $(t', i')$ con $t' \ge t$ e $i' \ge i$ (vedi Alberi binari di ricercaAlbero binario di ricerca come albero binario proprio con entry nei nodi interni e foglie vuote; inorder crescente; TreeSearch; get, put e remove (due casi, con predecessore inorder) in Theta(h); altezza fino a n-1; esempi di inserimenti; alberi aumentati con campi size e max e algoritmi di conteggio e interrogazione in O(h).Alberi binari di ricerca →). La struttura aiuta in due modi:

• ordine delle chiavi: in un nodo $v$ con chiave $k$, se $k < t$ allora $v$ e tutto il suo sottoalbero sinistro hanno chiavi $< t$ e vanno scartati; si prosegue solo a destra. Se $k \ge t$, tutto il sottoalbero destro ha chiavi $> k \ge t$ e quindi basta il suo max;
• campo max: se v.max $< i$ nessuna entry di $T_v$ può avere intensità $\ge i$, e si scarta tutto il sottoalbero in tempo costante.

Esempio. Le entry $(t, i_t)$ sono $(10, 4)$, $(5, 7)$, $(15, 3)$, $(2, 2)$, $(8, 9)$, inserite in questo ordine: radice $10$; figli $5$ e $15$; $5$ ha figli $2$ e $8$. I campi max sono: $2 \to 2$, $8 \to 9$, $5 \to \max(7, 2, 9) = 9$, $15 \to 3$, radice $\to 9$.

• TFR$(t = 9, i = 8)$: radice: max $= 9 \ge 8$; la chiave $10 \ge 9$ ma il valore $4 < 8$: si prova a sinistra. Nodo $5$: max $= 9 \ge 8$; chiave $5 < 9$, si va solo a destra. Nodo $8$: max $= 9 \ge 8$; chiave $8 < 9$, si va a destra: foglia vuota, no. Tornati alla radice si prova a destra (nodo $15$): max $= 3 < 8$, no. Risultato: no (il terremoto di intensità $9$ è avvenuto al tempo $8 < 9$).
• TFR$(t = 7, i = 8)$: radice $\to$ nodo $5$ (chiave $5 < 7$, solo a destra) $\to$ nodo $8$: chiave $8 \ge 7$ e valore $9 \ge 8$: yes.

(b) Input e output

Input: un nodo $v$ di $T$ (alla prima chiamata la radice; null/foglia esterna per il sottoalbero vuoto), un tempo $t$, un'intensità $i$. Output: yes se $T_v$ contiene una entry con chiave $\ge t$ e valore $\ge i$, no altrimenti.

(c) Pseudocodice

Algoritmo TFR(v, t, i)
Input: nodo v di T (null se il sottoalbero è vuoto), tempo t, intensità i
Output: yes se in T_v c'è una entry (t', i') con t' >= t e i' >= i, no altrimenti
if v = null OR v.max < i then return no
if v.key >= t then
    if v.value >= i then return yes
    if TFR(v.left, t, i) = yes then return yes
return TFR(v.right, t, i)

Chiamata: TFR(T.root(), t, i). Correttezza (induzione sull'altezza di $v$): se $v$ è vuoto o v.max $< i$ la risposta è no; altrimenti, se $v.key \ge t$, $v$ stesso è una entry valida quando $v.value \ge i$; il sottoalbero sinistro può contenere chiavi $\ge t$ (si cerca ricorsivamente); il destro ha tutte le chiavi $\ge t$ e si cerca ricorsivamente. Se $v.key < t$, né $v$ né il suo sottoalbero sinistro possono contenere chiavi $\ge t$ e si cerca solo a destra.

(d) Complessità

Sia $h$ l'altezza di $T$. I nodi in cui l'algoritmo prosegue "a cavallo" di $t$ formano un unico cammino dalla radice (a sinistra quando $v.key \ge t$, a destra quando $v.key < t$). Da ciascun nodo del cammino con $v.key \ge t$ parte una seconda chiamata sul figlio destro, che ha tutte le chiavi $\ge t$:

• se il suo max è $< i$ la chiamata termina subito con no in $O(1)$;
• altrimenti nel sottoalbero esiste una entry valida, e la discesa lungo i nodi con max $\ge i$ (controllo del valore, poi a sinistra se il max di sinistra è $\ge i$, altrimenti a destra) la trova restituendo yes dopo al più $h$ passi; quando ciò accade tutta la ricorsione termina.

In totale $O(h) + O(h) = O(h)$ operazioni, ciascuna $\Theta(1)$. La complessità è $O(h)$: $O(\log n)$ se l'albero è bilanciato, $O(n)$ nel caso pessimo di albero a catena. (Verificato su 500 alberi casuali confrontando il risultato con la ricerca esaustiva.)

Errori comuni

• Visitare tutto l'albero ($\Theta(n)$) senza sfruttare né l'ordine né max.
• Usare solo il campo max e ignorare la condizione sul tempo (si restituirebbe yes per un terremoto troppo vecchio).
• Cercare nel sottoalbero sinistro quando $v.key < t$ (inutile) o dimenticare di cercare a sinistra quando $v.key \ge t$ e $v.value < i$.
• Non specificare cosa fa l'algoritmo su un sottoalbero vuoto.