Albero di Ricerca Binaria (BST)

Albero di Ricerca Binaria (BST)

Alberi di ricerca: mantengono l'ordine relativo alla posizione dei sottoalberi e alla relazione sui nodi (permettono dunque di condurre ricerche in odo efficace).

Alberi binari di ricerca: dato un insieme di valori discreto per cui sia possibile effettuare un ordinamento, voglio cercare se un certo valore è presente nell'insieme.

		Sottoalbero Sinistro				Sottoalbero Destro

BST: proprietà per la quale, scelto un root, tutti gli elementi di sinistra vengono prima nell'ordine, mentre tutti gli elementi a destra vengono dopo (garantisce un attraversamento in intr ordine dell'albero e dispone gli elementi in ordine crescente).

Definizione per ricorsione

Albero vuoto = BST;

Albero con un solo nodo = BST;

Albero non vuoto e senza foglie = BST

root > radice del sottoalbero di sinistra;

root < radice del sottoalbero di destra;

Costruzione di un albero BST:

Prendo un sottoalbero vuoto;

Aggiungo un nodo:

se l'albero è vuoto, X = radice dell'albero;

se X < radice, aggiungo nel sottoalbero sinistro;

se X > radice, aggiungo nel sottoalbero destro;

Applico la procedura ai 2 sottolivelli,finché non si giunge alle foglie.

Ricerca in un BST

Se l'albero è vuoto No

SI     se xr = x NO   se xr x

Se l'albero non è vuoto si ha:

Se è foglia (x_r)

Se non è foglia, passo la domanda all'albero di sinistra (x < x_r) o a quello di destra (x > x_r)

NB: n = 2^{h + 1} - 1 n + 1 = 2^{h + 1} log₂(n + 1) - 1

C'è la complessità minima per d = 2 con un albero vicino all'albero completo si ha una complessità minore (da lineare a logaritmica), per questo in BST è più efficace.

Cancellazione di un nodo

Dobbiamo cancellare un nodo ed ottenere un albero ancora BST.

Se un albero è foglia e tolgo un nodo albero vuoto (BST);

Se rimuovo una foglia l'albero risultante è ancora BST;

Se ho sottoalberi e tolgo la radice:

se uno dei due sottoalberi è vuoto, basta dire che il sottoalbero non vuoto diventa il nuovo albero;

se entrambi gli alberi sono non vuoti:

Il LUB è una foglia o la radice di un albero il cui sottoalbero sinistro è vuoto;

Il LDB è una foglia o la radice di un albero il cui sottoalbero destro è vuoto;

Devo quindi trovare il LUB e ristrutturare il sottoalbero di destra (viceversa per quanto riguarda il LDB), vado poi a destra e continuo la ricerca del LUB nei sottoalberi di sinistra, finché non trovo dei sottoalberi vuoti il LUB è la radice del primo sottoalbero vuoto. Si sostituisce il LUB al nodo da tagliare.

Procedura ricorsiva per calcolare l'altezza di un albero:

se è vuoto, h = - 1;

se è foglia, h = 0;

altrimenti, h = 1 + max (h_sinistra, h_destra)

Inserimento in un BST

se l'albero è vuoto, inserire il nuovo elemento alla radice ed esci;

sia p la radice;

sia k < p, e il nodo in p non ha un figlio sinistro, inserisci il nuovo elemento come figlio sinistro ed esci;

sia k < p, e il nodo in p ha un figlio sinistro, allora cambia con p il figlio sinistro di p e torna al passo 3;

se il nodo in p non ha un figlio destro, inserisci il nuovo elemento come figlio destro ed esci;

se il nodo in p ha un figlio destro, allora cambia con p il figlio destro di p e torna al passo 3;

Tempo medio di Ricerca: il tempo richiesto per eseguire l'algoritmo di ricerca è proporzionale a h+1 (con h = altezza dell'albero).