Rappresentazione posizionale (Alberi Binari)

---

Index

1. Introduzione
2. Spazio
3. Svantaggi

Related

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

---

Introduzione

I nodi vengono memorizzati in un vettore, nel quale

• La radice occupa la posizione di indice $0$
• Il figlio sinistro è in posizione $2i+1$
• Il figlio destro è in posizione $2i+2$

Dove con $i$ si indica la posizione del nodo padre.

Esempio

oss: Posizione dell’elemento f è $5$, la posizione del suo figlio sinistro h è $2\cdot 5+1=11$

Rappresentazione Heap

Questa rappresentazione è utilizzata dalla Heap (Struttura Dati)

---

Spazio

Lo spazio da allocare in memoria dipende dall’altezza dell’albero (non dal numero di nodi)

Formula

n = $2^{n+1}-1$

Dove $n$ è il numero possibile di nodi di un albero con altezza $h$

---

Svantaggi

Un Albero Binario a rappresentazione posizionale richiedi di allocare in memoria un vettore capace di rappresentare un albero completo di grandezza $2^{h+1}-1$ dove $h$ è l’altezza dell’albero.

Quindi lo spazio occupato in memoria non dipende dal numero effettivo di elementi dell’albero ma dalla lunghezza dal cammino più lungo dalla radice ad una foglia (ovvero l’altezza)

In casi di alberi poco densi questo porta a un notevole spreco di spazio

Esempio

h = 3 Spazio Occupata: $2^{h+1}-1=2^{3+1}-1=15$ Spazio Utilizzato = 4 Spazio inutilizzato: 15 - 4 = 11

---

Metodi

Leggi: Operazioni su diverse rappresentazioni di alberi binari a confronto

---