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
-
Esercitazione su Minimum Spanning trees
-
Riassunto esame Algoritmi e strutture dati, Prof. Cabodi Giampiero, libro consigliato Appunti di Algoritmi e strutt…
-
Appunti di Strutture dati e algoritmi
-
Appunti di algoritmi e strutture dati