Binary search trees - Algoritmi e strutture dati

Binary Search Trees (BST)

Gli alberi binari di ricerca sono una implementazione

particolare della symbol table che combina la flessibilità

di inserimento delle liste concatenate e l’efficienza di

ricerca in un array ordinato.

Un albero binario di ricerca è un albero dove ogni nodo

contiene i puntatori agli altri due nodi, possibilmente

questi possono essere nulli, il che vuol dire che quel

ramo dell’albero non è completo. Se un nodo ha

entrambi i puntatori nulli ai figli è detto foglia. La

caratteristica di un albero di ricerca è che tutti i nodi nel

sottoalbero convenzionalmente di sinistra hanno chiavi

minori della chiave contenuta nel nodo di partenza, tutti

i nodi contenuti nel sottoalbero di destra hanno chiavi

maggiori del nodo di partenza, questo è un criterio più

restrittivo delle priority queue le quali invece richiedono

che i figli abbiano una certa relazione con il nodo padre,

non il sottoalbero, qui chiediamo che tutto il sottoalbero

abbia una relazione con il padre.

Vediamo degli esempi:

A sinistra abbiamo un albero binario, il nodo che non è

referenziato da nessuno -quello più in alto- si chiama

radice, left link è il collegamento sinistro, l’altro è quello

destro, abbiamo poi un sottoalbero il nodo “right child of

root” è il figlio destro della radice e le indicazioni senza

nodi collegati indicano dei puntatori nulli, quindi quelle

che non hanno nemmeno un figlio sono dette foglie.

A destra abbiamo un albero binario, esso ha la

caratteristica che il valore dei nodi di tutto quello che sta

nel sottoalbero sinistro è inferiore del valore del nodo

radice o genitore. Possiamo associare un numero a un

nodo, spesso è utilizzato per sapere quanti valori ci sono

nel sottoalbero, si dice che i nodi vengono etichettati,

quindi della struttura dati oltre alla chiave che è scritta

all’interno del nodo e al valore che noi non

rappresentiamo ma che da qualche parte ci sarà

abbiamo anche la possibilità di avere una variabile

tanking ausiliare

Binary search trees – search

Vediamo come funziona la ricerca all’interno dell’albero:

Partiamo sempre dal nodo radice che è identificato

all’interno della struttura dati, dopodichè confrontiamo la

chiave che stiamo cercando con quella del nodo

corrente, che è il nodo radice, se sono uguali abbiamo

trovato il risultato che cercavamo, altrimenti sono

maggiori o minori, allora se ad esempio sto cercando la

R, come nell’esempio riportato, siccome R<S allora vado

a cercarla nel sottoalbero di sinistra perché so che tutte

le chiavi minori di S se ci sono sono lì, quindi butto via il

sottoalbero di destra, siccome ora E non è uguale a R ma

R>E allora butto via il sottoalbero di sinistra, a questo

punto ho trovato un search heap, quindi un centro,

perché ho trovato un nodo etichettato R quando stavo

cercando R.

A ogni passaggio ho evitato di esaminare parti

dell’albero che non sono di mio interesse.

Se però sto facendo una ricerca nel caso di una chiave

che non c’è, l’esempio è riportato nell’immagine a

destra, parto dalla S e voglio cercare la T, essendo T>S

la cerco nel sottoalbero di destra, arrivo alla X, essendo

T<X dovrebbe stare nel sottoalbero di sinistra della X ma

ho un puntatore nullo, se nella mia ricerca finisco per

non trovare la chiave e incontro un puntatore nullo la

mia ricerca si ferma con un miss.

Notiamo che in entrambi i casi se l’albero è ben fatto il

numero di confronti che faccio è abbastanza limitato.

Binary search trees – insertion

L’inserimento è più complicato perché devo trovare il

posto giusto per l’inserimento, quindi creare un nuovo

nodo nell’albero, e poi devo anche collocarlo nel punto

corretto sistemando l’albero, si parla di ristrutturazione

dell’albero.

Faccio in questo caso una ricerca di dove dovrebbe stare

L, perché se trovo N cambio il valore perché le chiavi

sono uniche quindi se trovo qualcosa che è già L cambio

solo il valore, se non c’è devo creare il nodo e sistemare

l’albero di conseguenza.

Guardiamo intuitivvamente al tempo di esecuzione di

questa operazione:

Se l’albero è bilanciato come nel caso di sinistra allora la

mia ricerca si trova nel caso migliore perché la

profondità dell’albero è minima, quindi ho un numero di

livelli tutti riempiti al massimo -magari eccetto l’ultimo-,

quindi la mia profondità sarà log(N) e i confronti saranno

N+1.

L’albero binario però potrebbe essere non bilanciato

come nel caso intermedio, qui il terzo livello è non

completo. In questo caso tipico non è che debba fare

molte discese ma sicuramente più confronti di quanti ne

faccio nel caso migliore.

Nel caso peggiore vado a costruire l’albero binario ma

ogni livello è popolato da un unico nodo, quindi alla fine

ho una catena che contiene N nodi, mi sono riportato nel

caso della lista sequenziale. Quando faccio inserimenti e