Visite Alberi (preorder, inorder, postorder)

---

Index

1. Introduzione
2. Visita in preordine (preorder)
3. Visita inordine (inorder)
4. Visita postordine (postorder)
5. Visite per Livelli
6. Costo temporale delle visite

Related

• Introduzione agli Algoritmi (class)
• Alberi (Struttura Dati)

---

Introduzione

L’accesso progressivo a tutti i nodi di un albero si chiama visita dell’albero.

Tipi di visite

Nel caso degli alberi binari, nei quali i figli di ogni nodo (e quindi i sottoalberi) sono al massimo due, le possibili decisioni in merito a questa scelta danno luogo a tre diverse visite:

• Visita in preordine (preorder)
• Visita inordine (inorder)
• Visita postordine (postorder)

Esempio

• Preordine: $\left[\text{a - f - z - g - b - g}\right]$
• Inordine: $\left[\text{z - f - g - a - b - k}\right]$
• Postordine: $\left[\text{z - g - f - k - b - a}\right]$

---

Visita in preordine (preorder)

Nella visita in preordine il nodo è visitato prima di proseguire la visita nei suoi sottoalberi.

Ordine

Esempio: $\left[\text{a - f - z - g - b - g}\right]$

Esempio Stampa

def StampaABPreorder(p):
  if p == none: return None
  
  print(p.key)
  StampaABPreorder(p.left)
  StampaABPreorder(p.right)

---

Visita inordine (inorder)

Nella visita inordine il nodo corrente è visitato dopo la visita del sottoalbero sinistro e prima di quella del sottoalbero destro.

Ordine

Esempio: $\left[\text{z - f - g - a - b - k}\right]$

Esempio Stampa

def StampaABInorder(p):
  if p == none: return None
  
  StampaABPreorder(p.left)
  print(p.key)
  StampaABPreorder(p.right)

---

Visita postordine (postorder)

Nella visita in postordine il nodo corrente è visitato dopo entrambe le visite dei sottoalberi.

Ordine

Esempio: $\left[\text{z - g - f - k - b - a}\right]$

Esempio Stampa

def StampaABPostorder(p):
  if p == none: return None
  
  StampaABPreorder(p.left)
  StampaABPreorder(p.right)
  print(p.key)

---

Costo temporale delle visite

Indipendentemente del tipo di visita che utilizziamo, visitare interamente un albero binario un albero binario richiede $\Theta (n)$.

Nel caso di un albero binario rappresentato attraverso un record a puntatori, l’ equazione di ricorrenza della visita dell’albero è:

$$\begin{array}{rl}& T(n)=T(k)+T(n-k-1)+\Theta (1)\\ & T(1)=\Theta (1)\end{array}$$

Risoluzione per Metodo Sostituzione

Leggi Teoria Metodo Sostituzione

• Esempio pratico: link

Dimostrare $T(n)\in \Theta (n)$ ovvero:

• $T(n)\le c\cdot n$ ($O$)
• $T(n)\ge c\cdot n$ ($\Omega$)

Eq. Ricorrenza Senza Asintotica

$$\begin{array}{rl}& T(n)=T(k)+T(n-k-1)+b\\ & T(1)=a\end{array}$$

Dimostrazione $O$

Dimostrare: $T(n)\le c\cdot n$

Caso Base $(n=1)$

$$\begin{array}{rl}& T(n)\le c\cdot n\\ & T(1)\le c\cdot 1\\ & a\le c\end{array}$$

Ipotesi Induttiva

• $T(k)\le c\cdot k$
• $T(n-1-k)\le c\cdot (n-1-k)$

Passo Induttivo

$$\begin{array}{rlr}& T(n)\le c\cdot n& \\ & T(k)+t(n-1-k)+b\le c\cdot n& \\ & \cancel{ck}+\cancel{cn}-c-\cancel{ck}+b\le \cancel{cn}& \\ & b\le c& \end{array}$$

Quindi: $T(n)\in O(n)$

Dimostrazione $\Omega$

Dimostrare: $T(n)\ge c\cdot n$

Caso Base $(n=1)$

$$\begin{array}{rl}& T(n)\ge c\cdot n\\ & T(1)\ge c\cdot 1\\ & a\ge c\end{array}$$

Ipotesi Induttiva

• $T(k)\ge c\cdot k$
• $T(n-1-k)\ge c\cdot (n-1-k)$

Passo Induttivo

$$\begin{array}{rlr}& T(n)\ge c\cdot n& \\ & T(k)+t(n-1-k)+b\ge c\cdot n& \\ & \cancel{ck}+\cancel{cn}-c-\cancel{ck}+b\ge \cancel{cn}& \\ & b\ge c& \end{array}$$

Quindi: $T(n)\in \Omega (n)$

Dimostrazione $\Theta$

Visto che $\exists c_{1}t.c.T(n)\le c_1\cdot n$ e $\exists c_{2}t.c.T(n)\ge c_2\cdot n$

• Allora $T(n)\in \Theta (n)$

---

Visite per Livelli

---

Applicazione delle visite

Le visite sono estremamente utili per ispezionare l’albero e dedurne delle proprietà.

A seconda delle proprietà che si vuole esaminare può essere più utile una delle tre visite considerate

Esempi di visite: Esercizi visite alberi binari 🟢

---