Algoritmi e programmazione/Alberi binari di ricerca (BST)

Da WikiAppunti.
Jump to navigation Jump to search
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 9. Alberi binari di ricerca (BST).
/Alberi binari di ricerca (BST)}}  [[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Alberi binari di ricerca (BST)}}/Le tabelle di simboli{{#ifcategory:Traduzioni|/Alberi binari di ricerca (BST)||/Alberi binari di ricerca (BST)}}|8. Le tabelle di simboli]]/Alberi binari di ricerca (BST)}}  [[{{#ifcategory:Traduzioni|/Alberi binari di ricerca (BST)|Algoritmi e programmazione|/Alberi binari di ricerca (BST)}}|{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Alberi binari di ricerca (BST)}}]][[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Alberi binari di ricerca (BST)}}/Tipologie di problemi{{#ifcategory:Traduzioni|/Alberi binari di ricerca (BST)||/Alberi binari di ricerca (BST)}}|10. Tipologie di problemi]]  /Alberi binari di ricerca (BST)}}

Operazioni su alberi binari[modifica | modifica sorgente]

Attraversamento di un albero binario[modifica | modifica sorgente]

Attraversamento albero binario.png
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[modifica | modifica sorgente]

  • 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)[modifica | modifica sorgente]

4 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 | modifica sorgente]

Search[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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

Sort[modifica | modifica sorgente]

15 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 | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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,[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 | modifica sorgente]

20 Tutte queste operazioni, tranne la visita (sopra denominata "sort"), sui BST sono di complessità lineare[2] rispetto all'altezza dell'albero: <math>T \left( n \right) = O \left( h \right)</math> → rispetto a n. Il BST è vantaggioso tanto più l'albero è bilanciato:

  • caso migliore: <math>h= \log_2{n} \Rightarrow T \left( n \right) =O \left( \log{n} \right)</math> (albero completamente bilanciato)
  • caso medio: <math>T \left( n \right) \simeq O \left( \log{n} \right)</math>
  • caso peggiore: <math>h=n \Rightarrow T \left( n \right) =O \left( n \right)</math> (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 | modifica sorgente]

Rotate a destra/sinistra[modifica | modifica sorgente]

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[modifica | modifica sorgente]

Inserimento alla radice[modifica | modifica sorgente]

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

Partition[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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

Note[modifica | modifica sorgente]

  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.
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 9. Alberi binari di ricerca (BST).
/Alberi binari di ricerca (BST)}}  [[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Alberi binari di ricerca (BST)}}/Le tabelle di simboli{{#ifcategory:Traduzioni|/Alberi binari di ricerca (BST)||/Alberi binari di ricerca (BST)}}|8. Le tabelle di simboli]]/Alberi binari di ricerca (BST)}}  [[{{#ifcategory:Traduzioni|/Alberi binari di ricerca (BST)|Algoritmi e programmazione|/Alberi binari di ricerca (BST)}}|{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Alberi binari di ricerca (BST)}}]][[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Alberi binari di ricerca (BST)}}/Tipologie di problemi{{#ifcategory:Traduzioni|/Alberi binari di ricerca (BST)||/Alberi binari di ricerca (BST)}}|10. Tipologie di problemi]]  /Alberi binari di ricerca (BST)}}