Esercizio 8indici del level numbering

Esame

In questa pagina 5

Testo (esempio di tema d'esame, seconda parte, esercizio 1, 5 punti). Dato un albero binario proprio $T$ , si definisce il level numbering dei nodi di $T$ come segue:

se $v$ è radice di $T$ , allora l'indice $\ell(v)$ di $v$ nel level numbering è $1$ ;
se $v$ non è radice, sia $u$ il padre di $v$ : allora $\ell(v) = 2\,\ell(u)$ se $v$ è figlio sinistro di $u$ , e $\ell(v) = 2\,\ell(u) + 1$ se $v$ è figlio destro di $u$ .

Si vuole progettare un algoritmo ricorsivo che salvi in un campo v.indexLN l'indice $\ell(v)$ di $v$ nel level numbering, per ogni nodo $v \in T$ .

(a) Si fornisca lo pseudocodice per l'algoritmo richiesto. (b) Si analizzi la complessità dell'algoritmo.

Per ricevere il massimo dei punti l'algoritmo deve avere complessità in tempo $O(n)$ , dove $n$ è il numero di nodi di $T$ .

Idea

L'indice di un nodo dipende solo dall'indice del padre e dal lato. Il legame con la scrittura binaria (Sistemi di numerazione posizionali) è utile: moltiplicare per $2$ aggiunge uno zero a destra, moltiplicare per $2$ e sommare $1$ aggiunge un uno. Quindi $\ell(v)$ è il numero binario formato da un $1$ iniziale seguito, nell'ordine, dai passi dalla radice a $v$ ( $0$ = sinistra, $1$ = destra). Quindi il padre deve conoscere il proprio indice prima di passarlo ai figli: serve una visita in preorder in cui l'indice viene passato come parametro (non lo si ricalcola risalendo dai nodi: costerebbe $\Theta(\text{depth})$ per nodo, quindi fino a $\Theta(n^2)$ in totale; vedi Visite di alberi).

(a) Pseudocodice

Algoritmo levelNumbering(T, v, idx)
Input: albero binario proprio T, nodo v di T, intero idx = indice che v deve avere
Output: nessuno; side effect: v.indexLN = idx e lo stesso per ogni discendente di v
v.indexLN <- idx
if T.isInternal(v) then
    levelNumbering(T, T.left(v), 2 * idx)
    levelNumbering(T, T.right(v), 2 * idx + 1)

Chiamata iniziale: levelNumbering(T, T.root(), 1).

Correttezza (induzione sull'altezza di $v$ ). Se $v$ è una foglia imposta il proprio indice e termina: corretto. Se $v$ è interno, imposta idx (corretto per ipotesi sul parametro) e per l'ipotesi induttiva le chiamate sui figli assegnano correttamente i sottoalberi con i parametri $2\,idx$ e $2\,idx + 1$ , che sono per definizione gli indici dei figli.

(b) Complessità

L'albero della ricorsione ha un nodo per ogni nodo di $T$ (una chiamata per nodo, esattamente una) e ogni chiamata esegue un numero costante di operazioni, escluse le chiamate figlie: due moltiplicazioni, un'addizione, un'assegnazione e il test. Quindi

$t(n) \in \Theta(n).$

(Si assume che le operazioni su interi costino $\Theta(1)$ : con alberi molto profondi gli indici crescono come $2^{\text{depth}}$ e superano la parola di macchina.)

Esempio

Albero con radice $R$ , figlio sinistro $X$ (interno, con foglie $a$ e $b$ ) e figlio destro $Y$ (foglia): $\ell(R) = 1$ , $\ell(X) = 2$ , $\ell(Y) = 3$ , $\ell(a) = 4$ , $\ell(b) = 5$ .

chiamata	`idx` ricevuto	`v.indexLN` assegnato	chiamate figlie
`levelNumbering(T, R, 1)`	1	1	`X` con $2\cdot1=2$ , `Y` con $2\cdot1+1=3$
`levelNumbering(T, X, 2)`	2	2	`a` con $4$ , `b` con $5$
`levelNumbering(T, a, 4)`	4	4	nessuna (foglia)
`levelNumbering(T, b, 5)`	5	5	nessuna
`levelNumbering(T, Y, 3)`	3	3	nessuna

In binario: $\ell(b)=5=101_2$ , cioè $1$ (radice), poi $0$ (sinistra, verso $X$ ), poi $1$ (destra, verso $b$ ). Gli indici sono tutti distinti perché cammini diversi danno sequenze di bit diverse. Il caso estremo, un cammino tutto a destra di altezza $h$ , dà $1, 3, 7, \dots, 2^{h+1}-1$ (ogni passo a destra applica $x \mapsto 2x+1$ , e $1\to3\to7\to15$ sono i numeri $2^k-1$ ). Si riconosce la numerazione per livelli usata per l'array di uno heap (vedi Heap): i figli di $\ell$ sono $2\ell$ e $2\ell + 1$ . In un albero completo gli indici coincidono con le posizioni in $P[1..n]$ ; in un albero qualsiasi possono arrivare a $2^{h+1} - 1$ (cammino tutto a destra), il che mostra perché l'array è adatto solo agli alberi completi. (Verificato con alberi casuali: gli indici sono tutti distinti.)

Errori comuni

Calcolare $\ell(v)$ risalendo dai nodi al padre: $\Theta(n \cdot h)$ invece di $\Theta(n)$ .
Passare il valore del padre senza il fattore $2$ (o senza il $+1$ per il figlio destro).
Dimenticare la chiamata iniziale con indice $1$ (non $0$ ).
Chiamare ricorsivamente sui figli anche per una foglia (accede a figli inesistenti).

Versione ripasso

Testo. Albero binario proprio; $\ell(\text{radice}) = 1$ , figlio sinistro $2\ell(u)$ , destro $2\ell(u) + 1$ . Algoritmo ricorsivo che salva v.indexLN in tutti i nodi, in $O(n)$ .

Idea: l'indice del figlio dipende solo da quello del padre ⇒ preorder con l'indice passato come parametro (vedi Visite di alberi).
Pseudocodice: levelNumbering(T, v, idx): v.indexLN <- idx; se $v$ interno, levelNumbering(T, left(v), 2*idx) e levelNumbering(T, right(v), 2*idx+1); chiamata levelNumbering(T, T.root(), 1).
Correttezza: induzione sull'altezza di $v$ .
Complessità: una chiamata per nodo, costo costante: $\Theta(n)$ .
Esempio: $R=1$ , $X=2$ , $Y=3$ , $a=4$ , $b=5$ ; come l'array di uno heap (vedi Heap).
Nota: gli indici crescono come $2^{\text{depth}}$ (un cammino tutto a destra arriva a $2^{h+1} - 1$ ), quindi servono interi grandi per alberi molto profondi.
Errori: risalire al padre ( $\Theta(nh)$ ); fattore $2$ o $+1$ dimenticato; indice iniziale $0$ .

Esercizi su questo argomento

Esercizio 12 · inserimenti e rimozioni in uno heap