Summaries

Sono strutture gerarchiche in cui ad ogni oggetto (nodo padre) ha associato più oggetti (nodo figli). I figli hanno solo un padre tranne l'oggetto iniziale che costituisce la radice dell'albero. I nodi senza figli sono detti foglie e i nodi appartenenti allo stesso padre sono detti fratelli.

Caratteristiche degli alberi binari

• Livello di un nodo: la radice ha livello 1 ed ogni nodo N ha il livello p+1, dove p è il livello del nodo padre.

  

• Profondità: è il massimo livello dei suoi nodi. Ipotizzando di avere un albero binario di profondità K, possiamo ricavare il massimo numero di nodi cioè:

  • min = k
  • max = 2^k - 1

  Inoltre, in funzione del numero di nodi, è possibile ricavare la profondità minima e cioè O(log n).

• Albero pieno: un albero che ha tutti i nodi (2^k - 1) è detto pieno. Cioè tutti i nodi del penultimo livello hanno figli. Un esempio:

  

• Albero completo: tutti i livelli tranne l'ultimo sono riempiti e l'ultimo livello è riempito da sinistra a destra. Un esempio:

  

• Albero bilanciato: per ogni nodo la profondità del sotto-albero di sinistra differisce di al più uno dalla profondità del sotto-albero destro. DEVE VALERE PER OGNI SOTTO ALBERO.

  

Rappresentazione degli alberi

Strutture indicizzate

• Vettore dei padri:

  • PRO: rappresentazione di alberi generici, accesso diretto ad un qualunque nodo e accesso O(1) al padre
  • CONTRO: ricerca figli ha complessità O(Dim)

  

• Vettore posizionale: si può definire una formula che a partire dalla posizione (V) di un nodo posso conoscere i figli. P[V] => i-esimo figlio di V = P[dv+1]*

  • PRO: accesso in O(1) ai figli di un nodo, accesso ai padri attraverso formula inversa ⌊v/d⌋ e struttura compatta
  • CONTRO: alberi generici, spazio libero e stima della profondità per il dimensionamento dell'array

  

Rappresentazioni collegate (memoria dinamica)

1. SOLUZIONE: puntatore ai figli
2. SOLUZIONE: lista di figli
3. SOLUZIONE: primo figlio-fratello

Ad ogni nodo vengono associati 2 o più puntatori ai figli.

Nella prima soluzione i pro sono: accesso murato ai figli, accesso da un singolo punto e versatilità. Nella seconda e terza soluzione il contro è che hanno accesso tramite scorrimento delle liste ai figli.

La struttura più opportuna dipende dal programma che dobbiamo sviluppare.