Albero binario di ricerca
# Albero binario di ricerca

Un albero binario di ricerca (meglio noto come BST, dall'inglese Binary Search Tree), in informatica, è un particolare tipo di struttura dati. Permette di effettuare in maniera efficiente operazioni come: ricerca, inserimento e cancellazione di elementi.

## Definizione

Intuitivamente, un albero binario di ricerca ha le seguenti proprietà:

* Il sottoalbero sinistro di un nodo $x$ contiene soltanto i nodi con chiavi minori della chiave del nodo $x$
* Il sottoalbero destro di un nodo $x$ contiene soltanto i nodi con chiavi maggiori della chiave del nodo $x$
* Il sottoalbero destro e il sottoalbero sinistro devono essere entrambi due alberi binari di ricerca.

La definizione formale di un albero binario di ricerca è quella di un albero binario $T$ avente le seguenti tre proprietà, in cui si indica con $x.key$ la chiave (il valore) di un nodo $x\in T$:

* $\forall \;x\in T,x.key\in C$ dove $C$ è un insieme parzialmente ordinato
* $\forall \;x\in T,y\in T:y\in left(x)\to y.key\leq x.key$ dove $left(x)$ rappresenta il sottoalbero sinistro di un nodo $x\in T$
* $\forall \;x\in T,y\in T:y\in right(x)\to y.key>x.key$ dove $right(x)$ rappresenta il sottoalbero destro di un nodo $x\in T$

## Implementazione

In generale, l'implementazione di un albero binario di ricerca è uguale a quella di un albero binario, poiché la differenza tra le due strutture dati è data soltanto dalla distribuzione delle chiavi.

Ad esempio, in C l'implementazione di un albero binario di ricerca contenente dei semplici interi è uguale a quella di un albero binario contenente semplici interi:

## Complessità

| | Complessità al caso pessimo | Complessità al caso medio |
| - | - | - |
| Spazio | $O(n)$ | $O(n)$ |
| Ricerca | $O(n)$ | $O(h)$ |
| Inserimento | $O(n)$ | $O(h)$ |
| Cancellazione | $O(n)$ | $O(h)$ |

## Operazioni

Per le operazioni più comuni su un albero binario di ricerca contenente $n$ nodi, sfruttando anche le sue proprietà, sono stati trovati algoritmi con complessità nell'ordine di $O(h)$ con $h$ pari all'altezza dell'albero stesso, tranne che per la visita di tutti i nodi (svolta in complessità $O(n)$).

Essendo l'albero binario di ricerca un particolare tipo di albero binario, nel caso migliore si ha $h=\log _{2}n$ dove $n$ è il numero di nodi dell'albero.

### Inserimento di un elemento

L'inserimento di un elemento in un albero binario di ricerca deve essere fatta in maniera che l'albero risultante dopo l'inserimento rispetti sempre le proprietà strutturali e del contenuto.

L'algoritmo è simile a quello della ricerca. In pratica si svolge una ricerca fin quando non si esce dall'albero e l'ultimo nodo attraversato prima di uscire sarà il padre del nuovo elemento inserito. A questo punto si confronta il valore del padre con quello da inserire e si inserisce adeguatamente a sinistra o destra del padre il nuovo valore.

L'algoritmo ha quindi la stessa complessità algoritmica di quello di ricerca, e quindi $O(h)$ con $h$ la profondità dell'albero.

Un'implementazione d'esempio in pseudocodice è la seguente:

### Cancellazione di un elemento

La cancellazione di un elemento in un albero binario di ricerca non è un'operazione semplice. Per mantenere le sue proprietà anche dopo la cancellazione, bisogna distinguere 3 casi differenti.

L'algoritmo per la cancellazione di un elemento distingue i seguenti tre casi:

* Se il nodo è una foglia senza figli, basta cancellarlo dall'albero.
* Se il nodo invece ha un figlio solo, si elimina sostituendolo nella struttura dell'albero con il suo unico figlio.
* Se il nodo invece ha due figli si ricerca il suo successore, e si scambia i valori del nodo da cancellare e del successore trovato, cancellando poi solo quest'ultimo (che ha zero o un figlio solo).

L'operazione di cancellazione ha una complessità finale $O(h)$ dove $h$ è la profondità dell'albero.

Una implementazione dell'algoritmo in pseudocodice è la seguente:

### Visita

La visita è un'operazione che permette di esplorare tutti i nodi di un albero che discendono dalla radice. Esistono tre tipi di visita:

* Visita anticipata (o pre-visita/prefissa, corrispettivo di prefix)
* Visita simmetrica (o in-visita/infissa, corrispettivo di infix)
* Visita posticipata (o post-visita/postfissa, corrispettivo di postfix)

Poiché tutti i nodi vengono visitati una sola volta, la complessità algoritmica è pari a $O(n)$.

Una implementazione d'esempio in pseudocodice di visita simmetrica è la seguente:

Gli altri due tipi di visita sono del tutto simili e differiscono soltanto per la posizione del comando di stampa della chiave; nel caso della visita anticipata la stampa della chiave avviene prima delle due operazioni di visita a sinistra e a destra, mentre nella visita posticipata essa avviene alla fine.

### Ricerca di un elemento

La ricerca del nodo contenente un certo valore è una delle operazioni più frequenti su un albero binario di ricerca.

L'algoritmo di ricerca, espresso in forma iterativa, sfrutta le caratteristiche dell'albero e l'ordinamento delle chiavi per effettuare tale operazione in maniera efficiente. Esso funziona in maniera analoga alla ricerca binaria: confronta la chiave della radice dell'albero con quella da trovare e, finché non viene trovata, continua a svolgere la ricerca nel sottoalbero sinistro o destro, a seconda della chiave da cercare.

L'algoritmo a ogni passo ricorsivo scende un livello dell'albero, quindi è evidente che la sua complessità algoritmica è $O(h)$, dove $h$ è la profondità dell'albero.

Una implementazione dell'algoritmo in pseudocodice è la seguente:

## Implementare gli alberi di ricerca binari su array

Se non è necessario effettuare frequentemente operazioni di inserimento e cancellazioni o non è affatto necessario effettuarle e non si vuole usare troppa memoria è possibile implementare un albero di ricerca binario su un array ordinato, con la restrizione che il numero degli elementi sia $2^{n}-1$ con $n\in \mathbb {N}$.

L'immagine sopra mostra un albero di ricerca binario implementato su un array ordinato di 15 elementi, si comincia ponendo il centro dell'array come radice dell'albero e come sue foglie rispettivamente il centro della parte destra dell'array e il centro della parte sinistra dell'array, si continua applicando ricorsivamente il procedimento fino a che non sono stati coperti tutti gli elementi. Si ottiene quindi l'equivalente dell'albero:

L'algoritmo in pseudocodice per la ricerca di una chiave è il seguente:

