4° Anno TEORIA 2. Allocazione dinamica della memoria | Page 47

10: Allocazione dinamica della memoria Vers. 9.1 – Ottobre 2025

GLI ALBERI DEF: Un ALBERO A è un particolare tipo di GRAFO CONNESSO E SENZA CICLI

Un albero A gode SEMPRE delle seguenti 3 PROPRIETA’: 1. se un albero possiede n nodi allora conterrà n-1 archi( N. B. non è vero il viceversa): 2. due nodi qualsiasi in un albero sono sempre connessi da un unico cammino semplice; 3. rimuovendo un qualsiasi arco dell’ albero, la struttura dati risultante

- non è più connessa- rimane divisa in due strutture dati astratte non lineari che risultano essere anch’ esse alberi

I tipi più utili di alberi usati in informatica sono gli alberi con radice ossia quegli alberi ai quali ad un nodo detto“ radice” viene attribuito un significato speciale.

In un albero ogni nodo può essere considerato radice del sottoalbero che da esso trae origine. I nodi dai quali non vengono originati sottoalberi, vengono chiamate foglie.

Esempio di albero con radice

B

C

G

Nodi Foglie

Notazione: radice dell’ albero: foglie dell’ albero: nodi intermedi dell’ albero:

A H, I, D, E, G B, C, F

Gli alberi che considereremo saranno alberi ordinati( nei quali si possono distinguere gli elementi primo, secondo, … n-esimo secondo un determinato criterio) alberi per i quali l’ ordinamento dei sottoalberi è importante.

DEF. In un albero A si dice grado di un nodo il numero dei sottoalberi di quel nodo.

DEF. In un albero A si dice livello di un nodo il numero di nodi attraversati da un cammino semplice dalla radice al nodo. Se il nodo è la radice dell’ albero, il livello è uguale ad 1.

DEF. Si dice altezza o profondità h di un albero A la lunghezza( ossia il numero di nodi) del

cammino semplice più lungo esistente tra nodo radice e nodi foglie, escludendo dal conteggio il nodo radice.

Autore: Rio Chierego( email: riochierego @ libero. it- sito web: www. riochierego. it) Pag. 47