Skip Lists:A Probabilistic Alternative to Balanced Trees
需积分: 13 154 浏览量
2011-12-06
10:07:06
上传
评论
收藏 892KB PDF 举报
ARTICLES
Algorithms and
Data
Structures
Jeffrey Vitter
Editor
Skip Lists:
A Probabilistic
Alternative to
Balanced Trees
Skip lists are data structures thla t use probabilistic balancing rather than
strictly enforced balancing. As a result, the algorithms for insertion and
deletion in skip lists are much simpler and significantly faster than equivalent
algorithms for balanced trees.
William Pugh
Binary trees can be used for representing abstract data
types such as dictionaries and ordered lists. They work
well when the elements are inserted in a random order.
Some sequences of operations, such as inserting the
elements in order, produce degenerate data structures
that perform very poo.rly. If it were possible to ran-
domly permute the list of items to be inserted, trees
would work well with high probability for any input
sequence. In most cases queries must be answered on-
line, so randomly permuting the input is impractical.
Balanced tree algorithms rearrange the tree as opera-
tions are performed to maintain certain balance condi-
tions and assure good performance.
Skip lists are a probabilistic alternative to balanced
trees. Skip lists are balanced by consulting a random
number generator. Although skip lists have bad worst-
case performance, no input sequence consistently pro-
duces the worst-case performance (much like quicksort
when the pivot element is chosen randomly). It is very
unlikely a skip list data structure will be significantly
unbalanced (e.g., for a dictionary of more than 250 ele-
ments, the chance that a search will take more than
three-times the expeci.ed time is less than one in a
million). Skip lists have balance properties similar to
that of search trees built by random insertions, yet do
not require insertions to be random.
It is easier to balance a data structure probabilisti-
tally than to explicitly maintain the balance. For many
applications, skip lists are a more natural representa-
tion than trees, and they lead to simpler algorithms.
The simplicity of skip list algorithms makes them
easier to implement and provides significant constant
factor speed improvements over balanced tree and
This work was partially supported by an AT&T Bell Labs Fellowship and by
NSF grant CCR-8908900.
0 1990 ACM OOOl-O78z/9o/o6t,o-o668 $1.50
self-adjusting tree algorithms. Skip lists are also very
space efficient. They can easily be configured to require
an average of 1% pointers per element (or even less)
and do not require balance or priority information to be
stored with each node.
SKIP LISTS
We might need to examine every node of the list when
searching a linked list (Figure la). If the list is stored in
sorted order and every other node of the list also has
a pointer to the node two ahead of it in the list (Fig-
ure lb), we have to examine no more than [n/21 +
1 nodes (where n is the length of the list). Also giving
every fourth node a pointer four ahead (Figure lc) re-
quires that no more than rn/41 + 2 nodes be examined.
If every (27th node has a pointer 2’ nodes ahead (Fig-
ure Id), the number of nodes that must be examined
can be reduced to rlog,nl while only doubling the num-
ber of pointers. This data structure could be used for
fast searching, but insertion and deletion would be im-
practical.
A node that has k forward pointers is called a level k
node. If every (2’)th node has a pointer 2’ nodes ahead,
then levels of nodes are distributed in a simple pattern:
50 percent are level 1, 25 percent are level 2,
12.5
percent are level 3 and so on. What would happen if
the levels of nodes were chosen randomly, but in the
same proportions (e.g., as in Figure le)? A node’s ith
forward pointer, instead of pointing 2’-’ nodes ahead,
points to the next node of level i or higher. Insertions or
deletions would require only local modifications; the
level of a node, chosen randomly when the node is
inserted, need never change. Some arrangements of
levels would give poor execution times, but we will see
that such arrangements are rare. Because these data
structures are linked lists with extra pointers that skip
over intermediate nodes, I named them skip lists.
668
Communications
of
the AGM ]une 1990 Volume 33 Number 6
资源评论
