FANDOM


Nota disambigua
Il titolo di questa voce non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 9. Alberi binari di ricerca (BST).
Blue Glass Arrow RTL  8. Le tabelle di simboliCrystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  10. Tipologie di problemi
Gli appunti che seguono sono contenuti nella sottopagina /sub (modifica · cronologia · aggiorna)

Operazioni su alberi binariModifica

Attraversamento di un albero binarioModifica

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 parametriModifica

  • 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

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 baseModifica

SearchModifica

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/MaxModifica

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

SortModifica

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

SuccessorModifica

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.

PredecessorModifica

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.

InsertModifica

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.

SelectModifica

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

20 Tutte queste operazioni sui BST sono di complessità lineare[2] 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 servizioModifica

Rotate a destra/sinistraModifica

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 avanzateModifica

Inserimento alla radiceModifica

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

PartitionModifica

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.

DeleteModifica

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

NoteModifica

  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.
Blue Glass Arrow RTL  8. Le tabelle di simboliCrystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  10. Tipologie di problemi

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Inoltre su FANDOM

Wiki casuale