# Algoritmi/Alberi binari di ricerca (BST)

Algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaAlgoritmi/Copertina
* Gli algoritmiAlgoritmi/Gli algoritmi
* L'analisi di complessità degli algoritmiAlgoritmi/L'analisi di complessità degli algoritmi
* Gli algoritmi di ordinamentoAlgoritmi/Gli algoritmi di ordinamento
* Grafi e alberiAlgoritmi/Grafi e alberi
* La ricorsioneAlgoritmi/La ricorsione
* Il paradigma "divide et impera"Algoritmi/Il paradigma "divide et impera"
* Gli heapAlgoritmi/Gli heap
* Le tabelle di simboliAlgoritmi/Le tabelle di simboli
* Alberi binari di ricerca (BST)Algoritmi/Alberi binari di ricerca (BST)
* Tipologie di problemiAlgoritmi/Tipologie di problemi
* Le tabelle di hashAlgoritmi/Le tabelle di hash
* L'ADT grafo non orientatoAlgoritmi/L'ADT grafo non orientato
* Gli algoritmi di visita dei grafiAlgoritmi/Gli algoritmi di visita dei grafi
* Le applicazioni degli algoritmi di visita dei grafiAlgoritmi/Le applicazioni degli algoritmi di visita dei grafi
* Gli alberi ricoprenti minimiAlgoritmi/Gli alberi ricoprenti minimi
* I cammini minimiAlgoritmi/I cammini minimi
Modifica il sommario

## Operazioni su alberi binari
### Attraversamento di un albero binario
#### Strategie di visita degli alberi binari (Root = radice, L = sottoalbero sinistro, R = sottoalbero destro)

* pre order: Root, L, R
* in order: L, Root, R
* post order: L, R, Root
L'operazione di attraversamento ha complessità lineare.

### Calcolo ricorsivo di parametri

* numero di nodi: 1 Root + ricorsione(L) + ricorsione(R)
* altezza: 1 + altezza del sottoalbero maggiore (calcolata in modo ricorsivo)

## Alberi binari di ricerca (BST)

albero binario di ricerca = albero binario in cui, per ogni radice, si trovano nodi le cui chiavi sono minori o uguali nel sottoalbero sinistro e nodi le cui chiavi sono maggiori o uguali in quello destro → la radice è l'elemento di separazione tra dati (chiavi) minori a sinistra e maggiori a destra.

### Operazioni di base
#### Search

Ricerca una chiave, determinando a ogni radice il sottoalbero in cui cercare con un semplice confronto.

##### Casi di terminazione

* search hit: la chiave è stata trovata in una radice;
* search miss: la chiave non è stata trovata e si è giunti a un albero vuoto.

#### Min/Max

Ricerca il valore minimo/massimo, percorrendo tutti i sottoalberi sinistri/destri.

#### Sort (Visita)

Per ottenere l'ordinamento crescente delle chiavi basta visitare il BST in order. Per fare questo è necessario visitare tutti i nodi dell'albero: l'operazione ha quindi complessità lineare nel numero di nodi.

#### Successor

1º modo) Si ordinano i valori nell'albero con l'operazione Sort.
2º modo) Il successore è l'elemento che tra le chiavi più grandi ha la chiave più piccola → è il minimo del sottoalbero destro. Se il sottoalbero destro è vuoto, si cerca il primo antenato che abbia come figlio sinistro il nodo stesso o un suo antenato.

#### Predecessor

1º modo) Si ordinano i valori nell'albero con l'operazione Sort.
2º modo) Il predecessore è l'elemento che tra le chiavi più piccole ha la chiave più grande → è il massimo del sottoalbero sinistro. Se il sottoalbero sinistro è vuoto, si cerca il primo antenato che abbia come figlio destro il nodo stesso o un suo antenato.

#### Insert

Inserisce un nuovo elemento mantenendo le proprietà del BST. L'inserzione avviene sempre nelle foglie.
Se il BST è vuoto, crea un nuovo albero, altrimenti:
* inserzione ricorsiva: considera ricorsivamente terne L-Root-R, e a ogni passo effettua un confronto;
* inserzione iterativa: prima ricerca (search) la posizione in cui la chiave si dovrebbe trovare, quindi la inserisce in quella posizione.

#### Select

Dato un valore intero k, estrae/sceglie la k + 1-esima chiave più piccola nel BST (con k che parte da 0). Dopo aver associato a ogni nodo il numero delle chiavi contenute nei sottoalberi radicati in esso, a ogni terna L-Root-R determina se la chiave che si sta cercando può essere contenuta nel sottoalbero L in base al suo numero di chiavi associato t (per il sottoalbero sinistro vuoto: t = 0):
* se t = k: termina l'operazione di select e ritorna Root;
* se t > k: scende nel sottoalbero L;
* se t < k: scende nel sottoalbero R, ricercando la chiave di ordine k = k − t − 1.

#### Complessità

Tutte queste operazioni, tranne la visita (sopra denominata "sort"), sui BST sono di complessità lineare rispetto all'altezza dell'albero: $T\left(n\right)=O\left(h\right)$ → rispetto a n. Il BST è vantaggioso tanto più l'albero è bilanciato:
* caso migliore: $h=\log _{2}{n}\Rightarrow T\left(n\right)=O\left(\log {n}\right)$ (albero completamente bilanciato)
* caso medio: $T\left(n\right)\simeq O\left(\log {n}\right)$
* caso peggiore: $h=n\Rightarrow T\left(n\right)=O\left(n\right)$ (albero completamente sbilanciato)
Effettuando tante operazioni su un BST bilanciato, il BST si potrebbe però sbilanciare:
1ª soluzione) ogni tanto si ribilancia il BST → poco efficace, perché si aggiunge la complessità dell'operazione di ribilanciamento;
2ª soluzione) si costruisce un albero bilanciato per costruzione, applicando dei vincoli.

### Operazioni di servizio
#### Rotate a destra/sinistra

Si scambia il rapporto padre-figlio tra due nodi x e y, posizionando opportunamente i sottoalberi di partenza dei nodi attraverso semplici spostamenti dei puntatori ai sottoalberi.

### Operazioni avanzate
#### Inserimento alla radice

Inserisce la chiave con l'operazione Insert, quindi effettua delle rotazioni per spostare progressivamente la nuova chiave dal basso verso la radice.

#### Partition

Riorganizza l'albero intorno a una certa chiave di ordine k (Select), portandola alla radice (Rotate). Se applicata intorno alla chiave mediana, spesso permette di ribilanciare un BST.

#### Delete

* nodo senza figli (foglia): si può cancellare subito la foglia;
* nodo con 1 figlio: basta connettere il figlio del nodo con il padre del nodo;
* nodo con 2 figli: bisogna sostituirlo o con il suo predecessore o con il suo successore:
** Precedessor/Successor: si ricerca il predecessore/successore in uno dei sottoalberi;
** Partition: lo si fa galleggiare fino alla radice;
** lo si connette con l'altro sottoalbero.

## Note

* ↑ Si calcola in questo modo: ogni foglia è costituita da 1 chiave; procedendo dal basso verso l'alto (bottom-up), si somma a ogni passo le dimensioni dei sottoalberi e si aggiunge 1 per la radice.
* ↑ Ad esempio, nel caso peggiore i confronti dell'operazione di search vengono fatti fino in fondo all'albero.