Algoritmi e programmazione:Alberi binari di ricerca (BST)/sub

Operazioni su alberi binari

Attraversamento di un albero binario

2 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

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

Alberi binari di ricerca (BST)

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

Operazioni di base

Search

6 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

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

Sort

15 Per ottenere l'ordinamento crescente delle chiavi basta visitare il BST in order.

Successor

8 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

11 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

14 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

16 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à

20 Tutte queste operazioni 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

21-22 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

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

Partition

31 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

• 38 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.