Algoritmi/Alberi binari di ricerca (BST)

Indice del libro

Operazioni su alberi binari

modifica

Attraversamento di un albero binario

modifica
 
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

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

Alberi binari di ricerca (BST)

modifica

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

modifica

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

modifica

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

Sort (Visita)

modifica

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

modifica

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

modifica

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.

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.

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,[1] 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 = kt − 1.

Complessità

modifica

Tutte queste operazioni, tranne la visita (sopra denominata "sort"), sui BST sono di complessità lineare[2] rispetto all'altezza dell'albero:   → rispetto a n. Il BST è vantaggioso tanto più l'albero è bilanciato:

  • caso migliore:   (albero completamente bilanciato)
  • caso medio:  
  • caso peggiore:   (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

modifica

Rotate a destra/sinistra

modifica

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

modifica

Inserimento alla radice

modifica

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

Partition

modifica

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.

  • 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.
  1. 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.
  2. Ad esempio, nel caso peggiore i confronti dell'operazione di search vengono fatti fino in fondo all'albero.