Skip list
In informatica, una skip list è una struttura dati probabilistica per la memorizzazione di una lista ordinata di elementi. Essa utilizza una gerarchia di liste concatenate che connettono sottosequenze di elementi. Queste liste ausiliarie permettono di percorrere la lista con grande efficienza, paragonabile a quella di un albero di ricerca binario bilanciato.
Il livello più basso rappresenta la lista concatenata.
Ricerca
[modifica | modifica wikitesto]L'operazione di ricerca in una skiplist è paragonabile alla ricerca dicotomica su un array ordinato, in quanto il principio di funzionamento è molto simile. Per effettuare la ricerca su una skiplist si parte dalla lista di livello più alto, avanzando finché il valore del nodo successivo al corrente non è maggiore della chiave cercata, in tal caso si scende di livello. In questo modo infatti il nodo corrente ha sempre valore minore della chiave cercata, ed è inoltre sempre possibile scendere di livello visto che ogni livello è un sottinsieme di quello inferiore. La ricerca su una skiplist ha costo O(log n) in termini di tempo.
Inserimento
[modifica | modifica wikitesto]L'idea per l'inserimento in una skip list è di natura probabilistica. Sia h il numero di livelli della skip list, partendo dal livello 0 (la lista originale) si copia l'elemento in modo ordinato nella lista (cercandone la posizione tramite la ricerca sulla skiplist stessa, in tempo O(log n) ) si lancia una moneta, se si ottiene croce (0) si ripete l'operazione di copia e lancio sul livello superiore, se si ottiene testa (1) l'operazione di inserimento termina. Se lanciando h volte la moneta si ha sempre croce, viene creato un nuovo livello che ha come elementi solo la testa, il nuovo elemento e la coda.
Altri progetti
[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file sulla Skip list