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.

Esempi di alberi binari

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 al 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 di ranking 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 intuitivamente 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...