Visite di alberi

In questa pagina 6

Una visita accede a tutti i nodi di un albero eseguendo una operazione su ciascuno. Preorder e postorder sono schemi generali: l'operazione di "visita" si sostituisce con quella che serve al problema. Se l'albero è ordinato i figli si toccano nell'ordine dato.

Algoritmo preorder(T, v)                    Algoritmo postorder(T, v)
Input: nodo v di T                          Input: nodo v di T
visita v                                    foreach w in T.children(v) do
foreach w in T.children(v) do                   postorder(T, w)
    preorder(T, w)                          visita v

Chiamata iniziale: preorder(T, T.root()). Preorder: prima il padre, poi i sottoalberi dei figli. Postorder: prima i sottoalberi dei figli, poi il padre.

Complessità

L'albero della ricorsione (vedi Algoritmi ricorsivi) ha un nodo per ogni nodo di $T$ . Sia $t_u$ il costo della visita di $u$ e $c_u$ il numero di figli. La chiamata su $u$ costa $\Theta(1 + c_u) + t_u$ (il ciclo sui figli, escluse le chiamate ricorsive, più la visita). Poiché $\sum_u c_u = n - 1$ (vedi Alberi):

$t(n) = \sum_{u \in T} \big(\Theta(1 + c_u) + t_u\big) = \Theta\Big(n + \sum_{u \in T} t_u\Big).$

Se ogni visita costa $\Theta(1)$ si ha $\Theta(n)$ ; se $t_u \in \Theta(\log n)$ per ogni $u$ si ha $\Theta(n \log n)$ .

Esempi

Preorder: indice di un libro. Nodi = capitoli e sezioni, "visita" = stampa del titolo; il preorder produce l'indice nell'ordine di lettura (Capitolo 1, Sezione 1.1, Sezione 1.2, Sezione 1.2.1, ...). È anche il modo in cui i file system mostrano cartelle e file.

Postorder: spazio occupato. Ogni nodo ha size proprio (una directory non include i file contenuti). Si vuole in size lo spazio complessivo. Il padre ha bisogno dei totali dei figli già calcolati, quindi serve il postorder.

Algoritmo diskSpace(T, v)
Input: nodo v di T      Output: spazio totale del sottoalbero T_v (e aggiornamento di v.size)
foreach w in T.children(v) do v.size <- v.size + diskSpace(T, w)
return v.size

Esempio: /(1K) ha docs(1K; file di 3K e 10K) e src(1K; file main.c di 5K e cartella lib(1K) con util.c di 4K). Postorder: a.pdf, b.pdf, docs $= 1+3+10 = 14$ , main.c, util.c, lib $= 1+4 = 5$ , src $= 1+5+5 = 11$ , / $= 1+14+11 = 26$ K. Costo $\Theta(n)$ .

L'algoritmo height di Alberi è un altro postorder: la "visita" calcola l'altezza del nodo dalle altezze dei figli.

Memorizzare profondità e altezza di ogni nodo

Profondità v.depth: serve prima il padre, quindi un preorder con la profondità passata come parametro: visita(T, v, d): v.depth <- d, poi per ogni figlio visita(T, w, d+1); chiamata iniziale con $d = 0$ . Costo $\Theta(n)$ . Invocare depth da ogni nodo costerebbe invece $\Theta(\sum \text{depth})$ , fino a $\Theta(n^2)$ .
Altezza v.height: postorder: v.height <- 0; per ogni figlio $w$ dopo la chiamata ricorsiva v.height <- max(v.height, 1 + w.height). Costo $\Theta(n)$ .

Antenato comune più basso (LCA)

Dati $v, w$ in $T$ , $\text{LCA}(v, w)$ è l'antenato comune più profondo. Algoritmo: si calcolano $d_v = \text{depth}(v)$ e $d_w = \text{depth}(w)$ risalendo; si porta il nodo più profondo a salire di $|d_v - d_w|$ passi, poi si salgono insieme $v$ e $w$ finché coincidono. Costo $O(\text{depth}(v) + \text{depth}(w)) = O(h)$ , al caso pessimo $O(n)$ e senza strutture di appoggio.

Preorder e postorder insieme

Dato l'ordine di visita in preorder, non tutte le sequenze sono postorder possibili. Se in preorder $A$ è prima di $B$ e in postorder $A$ è dopo $B$ , allora $A$ è antenato di $B$ ; se $A$ precede $B$ in entrambi, $A$ sta a sinistra di $B$ (non è suo antenato). La radice è sempre la prima in preorder e l'ultima in postorder: lo si usa per escludere sequenze, come nell'Esercizio 6 · preorder e postorder compatibili.

Errori comuni

Usare il preorder quando il padre ha bisogno dei risultati dei figli (somma, altezza): serve il postorder.
Scrivere il costo come $\Theta(n \cdot c)$ con $c$ numero massimo di figli: è $\Theta(n)$ perché $\sum c_u = n - 1$ .
Calcolare depth da ogni nodo (quadratico) invece di passare la profondità nel preorder.

Versione ripasso

Preorder: visita $v$ , poi ricorsivamente i figli. Postorder: prima i figli, poi $v$ . Sono schemi generali da adattare (vedi Alberi).
Costo: $\Theta(n + \sum_u t_u)$ , con $t_u$ costo della visita di $u$ , perché la chiamata su $u$ costa $\Theta(1+c_u) + t_u$ e $\sum_u c_u = n-1$ . Con $t_u = \Theta(1)$ : $\Theta(n)$ .
Preorder: indice di un libro; v.depth passando $d$ come parametro ( $d+1$ ai figli), $\Theta(n)$ .
Postorder: diskSpace (somma dei figli nel padre), height e v.height. Esempio: / $= 1 + 14 + 11 = 26$ K.
LCA: si livellano le profondità (salendo del dislivello) e poi si sale insieme finché coincidono; $O(h) \le O(n)$ .
Compatibilità preorder/postorder: radice prima in preorder e ultima in postorder; $A$ prima di $B$ in preorder e dopo in postorder $\Rightarrow$ $A$ antenato di $B$ ; prima in entrambi $\Rightarrow$ $A$ a sinistra di $B$ .
Esempio disk space: /(1) con docs(1; file 3 e 10) e src(1; main.c 5 e lib(1) con util.c 4): lib $= 5$ , src $= 11$ , docs $= 14$ , / $= 26$ K.
Profondità in preorder: visita(T,v,d): v.depth <- d e visita(T,w,d+1) per ogni figlio; $\Theta(n)$ .
Errori: preorder dove serve il postorder; costo $\Theta(n \cdot c)$ ; depth da ogni nodo.