Introduzione
Gli alberi binari di ricerca sono delle particolari tipologie di alberi con nodi aventi al massimo due figli, dove il figlio sinistro deve avere un valore minore del padre e il figlio destro deve avere un valore maggiore del padre, i nodi con valori uguali al padre possono essere messi o tutti a destra o tutti a sinistra, solitamente si mettono a destra, ma è una scelta del programmatore.
E’ un albero binario anche un albero contenente un solo nodo o nessun nodo (empty tree o null tree)
La struttura di un nodo è composta essenzialmente da un dato e due puntatori, che servono a memorizzare gli indirizzi del figlio destro e sinistro.
Rappresentazione nella momoria
I vari nodi degli alberi binari vengono memorizzati in maniera simile ad una lista, quindi effettuando i “collegamenti” attraverso i puntatori.
In genere, a causa la sua struttura, non è possibile utilizzare un array perché richiederebbe un utilizzo troppo elevato di memoria, esistono comunque dei casi particolari di alberi che invece lo permettono (esempio gli Heap).
Tipo di un nodo
Come avevamo anticipato un nodo di un albero binario ha tre componenti essenziali:
– dato
– puntatore al figlio destro
– puntatore al figlio sinistro
Spesso troviamo in aggiunta anche il puntatore al corrispondente nodo padre e il numero del nodo (key), questo dipende dalle esigenze del programmatore.
struct node {
int info;
struct node *left;
struct node *right;
};Descrivere un albero binario
In un albero binario, o anche in un albero generico, possiamo identificare i suoi nodi, cioè gli elementi, la radice (root) ovvero il primo nodo (che non ha un padre) e le foglie, ovvero i nodi finali (che non hanno figli).
Le caratteristiche che identificano la struttura di un albero, sono la sua dimensione (size), la sua altezza (height).
Inoltre possiamo identificare anche la profondità (depth) di un suo nodo e l’altezza di un nodo.
- Dimensione: numero di nodi totali dell’albero
- Altezza albero: massima distanza di una foglia dalla radice
- Altezza nodo: massima distanza del nodo da una foglia
- Profondità: distanza dalla radice
Visitare un albero binario
Visitare il nodo di un albero significa raggiungerlo attraverso un cammino, per poi poter accedere al suo contenuto.
E’ possibile visitare un albero, quindi visitare i suoi nodi, attraverso varie metodologie che vengono scelte a seconda delle esigenze.
Descriviamo le tre più note: inorder, postorder e preorder.
La visita inorder prevede un cammino attraverso l’albero, che permette di accedere ai nodi visitando prima il sotto-albero sinistro, poi la radice e infine il sotto-albero destro.
Lo pseudocodice sottostante stamperà il contenuto dei nodi.
Inorder(u)
if(u != nil)
Inorder(u.left)
print(u.info)
Inorder(u.right)
La visita postorder prevede un cammino attraverso l’albero, che permette di accedere ai nodi visitando prima il sotto-albero sinistro, poi il sotto-albero destro e infine la radice.
Lo pseudocodice sottostante stamperà il contenuto dei nodi.
Postorder(u)
if(u != nil)
Postorder(u.left)
Postorder(u.right)
print(u.info)La visita preorder prevede un cammino attraverso l’albero, che permette di accedere ai nodi visitando prima la radice, poi il sotto-albero sinistro e infine il sotto-albero destro.
Lo pseudocodice sottostante stamperà il contenuto dei nodi.
Preorder(u)
if(u != nil)
print(u.info)
Preorder(u.left)
Preorder(u.right)Il costo del tempo per la visita dei nodi, supponendo che per ogni nodo venga effettuata un’operazione costante, è Θ(n).