Skip list
![Niente fonti!](http://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Question_book-4.svg/45px-Question_book-4.svg.png)
![Abbozzo](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0e/Puzzle_stub.svg/45px-Puzzle_stub.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/86/Skip_list.svg/470px-Skip_list.svg.png)
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
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
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
Altri progetti
- Wikimedia Commons
Wikimedia Commons contiene immagini o altri file sulla Skip list
V · D · M | |
---|---|
Tipi | Collezione · Container |
Astratte | Array associativo (Multimap) · Lista · Pila · Coda (Deque) · Coda di priorità · Set (Multiset · Mfset) |
Array | Bit array · Buffer circolare · Array dinamico · Hash table · Array sparso |
Collegate | Lista di associazioni · Lista concatenata · Skip list · Unrolled linked list · Lista concatenata tramite XOR |
Alberi | B-albero · Albero binario di ricerca (Albero AA · Albero AVL · RB-Albero · Albero binario di ricerca bilanciato · Albero splay) · Heap (Heap binario · Heap binomiale · Heap di Fibonacci) · Albero di Merkle · Albero SPQR · Albero PQ · Albero indicizzato binario |
Grafi | Diagramma binario di decisione · Digrafo aciclico · Automa a stati finiti deterministico aciclico |
Alberi di partizionamento dei dati spaziali | Albero quadramentale · M-tree · R-tree (R* tree · R+ tree) · X-tree |
Lista di strutture dati |