📄 s_skl.htm
字号:
<html>
<head>
<title>Skip Lists</title>
</head>
<body bgcolor="#ffffff">
<p align=right>
<a href="s_man.htm" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_man.htm" target="_top"><img src="c_man.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/c_man.gif" width=74 height=19 border=0></A>
</p>
<h1>Skip Lists</h1>
Skip lists are linked lists that allow you to <i>skip</i> to the correct
node. The performance bottleneck inherent in a sequential
scan is avoided, while insertion and deletion remain relatively
efficient. Average search time is <b><i>O</i></b>(lg <i>n</i>).
Worst-case search
time is <b><i>O</i></b>(<i>n</i>),
but is extremely unlikely. An excellent reference for skip lists is
<a href="javascript:if(confirm('http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_skip.pdf \n\nThis file was not retrieved by Teleport Pro, because it is linked too far away from its Starting Address. If you increase the in-domain depth setting for the Starting Address, this file will be queued for retrieval. \n\nDo you want to open it from the server?'))window.location='http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_skip.pdf'" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_skip.pdf" target="_top">Pugh [1990]</a>.
<h2>Theory</h2>
The indexing scheme employed in skip lists is similar in nature
to the method used to lookup names in an address book. To lookup
a name, you index to the tab representing the first character of
the desired entry. In Figure 3-8,
for example, the top-most list
represents a simple linked list with no tabs. Adding tabs
(middle figure) facilitates the search. In this case, level-1
pointers are traversed. Once the correct segment of the list is
found, level-0 pointers are traversed to find the specific entry.
<p>
<center>
<h3><a name="Fig3-8">
<img src="s_fig38.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_fig38.gif" vspace=5 width=520 height=232><br>
Figure 3-8: Skip List Construction</a>
</h3>
</center>
<p>
The indexing scheme may be extended as shown in the bottom
figure, where we now have an index to the index. To locate an
item, level-2 pointers are traversed until the correct segment of
the list is identified. Subsequently, level-1 and level-0
pointers are traversed.
<p>
During insertion the number of pointers required for a new
node must be determined. This is easily resolved using a
probabilistic technique. A random number generator is used to
toss a computer <i>coin</i>. When inserting a new node, the coin is
tossed to determine if it should be level-1. If you win, the
coin is tossed again to determine if the node should be level-2.
Another win, and the coin is tossed to determine if the node
should be level-3. This process repeats until you lose.
If only one level (level-0) is implemented, the data structure is a
simple linked-list with <b><i>O</i></b>(<i>n</i>) search time.
However, if sufficient levels are implemented, the skip list may be
viewed as a tree with the root at the highest level, and search time
is <b><i>O</i></b>(lg <i>n</i>).
<p>
The skip list algorithm has a probabilistic component, and
thus a probabilistic bounds on the time required to execute.
However, these bounds are quite tight in normal circumstances.
For example, to search a list containing 1000 items, the
probability that search time will be 5 times the average is about
1 in 1,000,000,000,000,000,000</a>.
<h2>Implementation</h2>
An
<a href="javascript:if(confirm('http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_skl.txt \n\nThis file was not retrieved by Teleport Pro, because it is linked too far away from its Starting Address. If you increase the in-domain depth setting for the Starting Address, this file will be queued for retrieval. \n\nDo you want to open it from the server?'))window.location='http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_skl.txt'" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_skl.txt">ANSI-C implementation</a>
for skip lists is included.
<b>Typedef T</b>
and comparison operators <b>compLT</b> and <b>compEQ</b> should be altered to
reflect the data stored in the list. In addition, <b>MAXLEVEL</b>
should be set based on the maximum size of the dataset.
<p>
To initialize, <b>initList</b> is called. The list header is
allocated and initialized. To indicate an empty list, all levels
are set to point to the header.
Function <b>insertNode</b>
allocates a new node,
searches for the correct insertion point, and inserts it in the list.
While searching, the <b>update</b> array
maintains pointers to the upper-level nodes encountered. This
information is subsequently used to establish correct links for
the newly inserted node. The <b>newLevel</b> is determined using a random
number generator, and the node allocated. The forward links are
then established using information from the <b>update</b> array.
Function <b>deleteNode</b> deletes and frees a node, and is implemented
in a similar manner.
Function <b>findNode</b> searches the list for a particular
value.
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -