Visite di alberi

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

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

Esempio. Sull'albero con radice $r$, figli $a$, $b$ e $c$ figlio di $a$: preorder $r,a,c,b$ e postorder $c,a,b,r$.

Sull'albero di riferimento di AlberiAlbero radicato (definizione per padre e ricorsiva), terminologia (antenati, discendenti, nodi interni ed esterni, sottoalbero, albero ordinato), profondità, livello, altezza; altezza = massima profondità delle foglie; algoritmi depth e height con costo; somma dei figli = n-1; esempio di algoritmo Omega(n^2) (heightBad).Alberi → ($r$; $a,b$ figli di $r$; $c,d$ figli di $a$; $e$ figlio di $d$) la traccia è:

In entrambi i casi ogni nodo compare una sola volta e $r$ è primo nel preorder e ultimo nel postorder. La ricorsione è quella di Algoritmi ricorsiviAlgoritmi ricorsivi come induzione eseguita; albero della ricorsione e record di attivazione nello stack; esempi ReverseArray, LinearSum, Power in tempo logaritmico, Fibonacci ricorsivo (esponenziale) e con memoizzazione; analisi della complessità con l'albero della ricorsione e correttezza per induzione.Algoritmi ricorsivi →: lo stack contiene il cammino dalla radice al nodo corrente, quindi occupa $\Theta(\text{altezza})$.

Complessità

Formula (complessità di una visita). L'albero della ricorsione (vedi Algoritmi ricorsiviAlgoritmi ricorsivi come induzione eseguita; albero della ricorsione e record di attivazione nello stack; esempi ReverseArray, LinearSum, Power in tempo logaritmico, Fibonacci ricorsivo (esponenziale) e con memoizzazione; analisi della complessità con l'albero della ricorsione e correttezza per induzione.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 AlberiAlbero radicato (definizione per padre e ricorsiva), terminologia (antenati, discendenti, nodi interni ed esterni, sottoalbero, albero ordinato), profondità, livello, altezza; altezza = massima profondità delle foglie; algoritmi depth e height con costo; somma dei figli = n-1; esempio di algoritmo Omega(n^2) (heightBad).Alberi →: ogni nodo non radice ha un solo padre, quindi gli archi sono $n-1$):

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

Esempio. In un albero con $n=7$ nodi $\sum_uc_u=n-1=6$, quindi $\sum_u(1+c_u)=2n-1=13$.

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

Il padre ha bisogno dei risultati dei figli esattamente come in una sommatoriaIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie → annidata: il totale di un nodo è la sua dimensione propria più i totali dei sottoalberi dei figli. 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 AlberiAlbero radicato (definizione per padre e ricorsiva), terminologia (antenati, discendenti, nodi interni ed esterni, sottoalbero, albero ordinato), profondità, livello, altezza; altezza = massima profondità delle foglie; algoritmi depth e height con costo; somma dei figli = n-1; esempio di algoritmo Omega(n^2) (heightBad).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)$ (in un albero ridotto a un cammino le profondità sono $0,1,\dots,n-1$ e la somma è $\frac{n(n-1)}{2}$, vedi SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →). Sull'albero di riferimento il preorder con $d$ assegna $r{:}0$, poi $a{:}1$, $c{:}2$, $d{:}2$, $e{:}3$, $b{:}1$.
• 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)

Definizione (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. La differenza di profondità è un valore assolutoIl valore assoluto è la distanza di un numero da zero: definizione, proprietà, disuguaglianza triangolare e disequazioni con i moduli.Valore assoluto (modulo) → perché non si sa quale dei due nodi sia più profondo. Perché funziona: dopo aver portato i due nodi alla stessa profondità, i loro antenati alla stessa profondità sono confrontabili e il primo in comune che si incontra salendo è, per definizione, il più profondo tra quelli comuni.

Traccia su $\text{LCA}(c,e)$ nell'albero di riferimento: $d_c=2$, $d_e=3$, differenza $1$; $e$ sale di un passo a $d$ (profondità $2$); ora $c\ne d$, salgono insieme: $c\to a$, $d\to a$; coincidono, quindi $\text{LCA}(c,e)=a$.

Esempio. Nell'albero con radice $r$, figli $a$, $b$ e $c$ figlio di $a$: $\text{LCA}(c,b)=r$ e $\text{LCA}(c,a)=a$.

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.