Alberi Binari (Struttura Dati)

---

Index

1. Introduzione
2. Completo e Quasi Completo
3. Caratteristiche
4. Tipi di Rappresentazione
5. Strutture dati implementate con Alberi Binari

Related

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

---

Introduzione

Un Albero Binario è un particolare tipo di Albero Ordinato, dove ogni nodo ha al massimo due figli.

Figlio sinistro e destro

Essendo alberi ordinati, i due figli di ciascun nodo si distinguono in figlio sinistro e figlio destro.

---

Completo e Quasi Completo

Albero Binario Completo

Tutti i livelli contengono il massimo numero possibile di nodi.

Albero Binario Quasi Completo

• Tutti i livelli tranne l’ultimo contengono il massimo numero possibile di nodi .
• L’ultimo livello è riempito completamente da sinistra verso destra solo fino ad un certo punto.

Non sono alberi quasi completi

---

Caratteristiche

In un Albero Binario Completo di altezza $h$:

• Il numeoro di foglie è $2^h$
• Il numero di nodi interni è $\sum _{i=0}^{h-1}{2}^i=2^h-1$
• il numero totale di nodi è $2^h+2^h-1=2^{h+1}-1$

Calcolare altezza h

Conoscendo il numero di nodi ($n$) di un albero binario completo possiamo calcolare l’altezza ($h$)

• Formula: $h={\log }_2\frac{n+1}{2}$

Dimostrazione

$$\begin{array}{rl}& n=2^{h+1}-1\\ & n+1=2^{n+1}\\ & {\log }_2(n+1)={\log }_2(2^{n+1})\\ & {\log }_2(n+1)=h+1\\ & h={\log }_2(n+1)-1\\ & h={\log }_2(n+1)-{\log }_2(2)\\ & h={\log }_2\frac{n+1}{2}\end{array}$$

In generale:

• Un albero binario completo ha $h=\Theta (\log n)$
• Un albero binario ha $h=\Omega (\log n)$

---

Tipi di Rappresentazione

Descriveremo ora tre diverse rappresentazioni dell’albero binario in memoria:

• Memorizzazione tramite puntatori 🟢
• Rappresentazione posizionale 🟢
• Rappresentazione tramite vettore dei padri 🟢

Leggi

• Operazioni su diverse rappresentazioni di alberi binari a confronto 🟢
• Visite Alberi (preorder, inorder, postorder) 🟢
• Esercizi visite alberi binari 🟢

---

Strutture dati implementate con Alberi Binari

• Alberi Binari di Ricerca

---