title: Albero binario di ricerca
text: # 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:
  
  