Albero binario di ricerca (Binary Search Tree)

Albero binario di ricerca (Binary Search Tree)

L’albero binario di ricerca, in ambito informatico, è un particolare tipo di struttura dati, di solito implementato come ADT (Abstract Data Type).
L’albero binario di ricerca è molto utilizzato in quanto possiede alcune peculiarità che gli permettono di essere particolarmente ottimo con gli algoritmi di ricerca; la sua struttura consiste in un nodo radice (root) con due campi puntatori per un ramo di albero sinistro ed uno destro, ciascun nodo sottostante possiede le stesse caratteristiche; se non bilanciato non è detto che un nodo abbia entrambi i figli, sia destro che sinistro, i nodi figli possono essere puntatori a NULL o in alternativa puntatori ad un nodo fittizio, utilizzato per segnalare che non esiste nodo figlio.
Ciascun nodo dell’albero ha la proprietà che sul sotto-albero sinistro abbia tutti i nodi con valore minore del suo, mentre nel sotto-albero destro abbia tutti i nodi con valore superiore al suo.
Bisogna fare attenzione, per quanto riguarda la complessità degli algoritmi che utilizzano questa struttura dati, che l’albero non degeneri in una lista, altrimenti non si hanno più vantaggi nell’utilizzo di questa struttura dati.

Es.

Struttura dati nodo albero

struct node{
int val;
struct node *leftchild;
struct node *rightchild;
}