Next: 3.8.1 Initialization:
Up: 3. Dictionaries
Previous: 3.7 Hash Table Restructuring
- REF.
- William Pugh. Skip Lists: A probabilistic alternative to
balanced trees. Communications of the ACM,
Volume 33, Number 6, pp. 668-676, 1990.
- Skip lists use probabilistic balancing rather than strictly
enforced balancing.
- Although skip lists have bad worst-case performance, no input
sequence consistently produces the worst-case performance (like
quicksort).
- It is very unlikely that a skip list will be significantly
unbalanced. For example, in a dictionary of more than 250 elements,
the chance is that a search will take more than 3 times the expected time
10-6.
- Skip lists have balance properties similar to that of search trees
built by random insertions, yet do not require insertions to be
random.
Figure 3.4:
A singly linked list
![\begin{figure}
\centerline{\psfig{figure=figures/Flist0.ps}}
\end{figure}](img118.gif) |
Consider a singly linked list as in Figure 3.4.
We might need to examine every node of the list when searching a
singly linked list.
Figure 3.5 is a sorted list where every other node has an additional
pointer, to the node two ahead of it in the list. Here we have to examine
no more than
![$ {\frac{n}{2}}$](img11.gif)
+1 nodes.
Figure 3.5:
Every other node has an additional pointer
![\begin{figure}
\centerline{\psfig{figure=figures/Flist1.ps}}
\end{figure}](img121.gif) |
Figure 3.6:
Every second node has a pointer two ahead of it
![\begin{figure}
\centerline{\psfig{figure=figures/Flist2.ps}}
\end{figure}](img122.gif) |
In the list of Figure 3.6, every second node has a pointer two ahead of
it; every fourth node has a pointer four ahead if it. Here we need to
examine no more than
![$ \lceil$](img119.gif)
![$ {\frac{n}{4}}$](img123.gif)
+ 2 nodes.
In Figure 3.7, (every
(2i)th node has a pointer (2i) node
ahead
(i = 1, 2,...); then the number of nodes to be examined can be
reduced to
log2n
while only doubling the number
of pointers.
Figure 3.7:
Every
(2i)th node has a pointer to a node (2i)nodes ahead
(i = 1, 2,...)
![\begin{figure}
\centerline{\psfig{figure=figures/Flist3.ps}}
\end{figure}](img124.gif) |
Figure 3.8:
A skip list
![\begin{figure}
\centerline{\psfig{figure=figures/Fskiplist1.ps}}
\end{figure}](img125.gif) |
Next: 3.8.1 Initialization:
Up: 3. Dictionaries
Previous: 3.7 Hash Table Restructuring
eEL,CSA_Dept,IISc,Bangalore