Algoritmi/Alberi binari di ricerca (BST)

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.