Java Reference
In-Depth Information
values are inserted, but it is rather complicated to implement. Chapter 13 presents
the AVL tree and the splay tree, which are also guaranteed to provide good per-
formance, but at the cost of added complexity as compared to the BST. The Skip
List is easier to implement than known balanced tree structures. The Skip List is
not guaranteed to provide good performance (where good performance is defined
as (log n) search, insertion, and deletion time), but it will provide good perfor-
mance with extremely high probability (unlike the BST which has a good chance
of performing poorly). As such it represents a good compromise between difficulty
of implementation and performance.
Figure 16.2 illustrates the concept behind the Skip List. Figure 16.2(a) shows a
simple linked list whose nodes are ordered by key value. To search a sorted linked
list requires that we move down the list one node at a time, visiting (n) nodes
in the average case. What if we add a pointer to every other node that lets us skip
alternating nodes, as shown in Figure 16.2(b)? Define nodes with a single pointer
as level 0 Skip List nodes, and nodes with two pointers as level 1 Skip List nodes.
To search, follow the level 1 pointers until a value greater than the search key
has been found, go back to the previous level 1 node, then revert to a level 0 pointer
to travel one more node if necessary. This effectively cuts the work in half. We
can continue adding pointers to selected nodes in this way — give a third pointer
to every fourth node, give a fourth pointer to every eighth node, and so on — until
we reach the ultimate of log n pointers in the first and middle nodes for a list of
n nodes as illustrated in Figure 16.2(c). To search, start with the bottom row of
pointers, going as far as possible and skipping many nodes at a time. Then, shift
up to shorter and shorter steps as required. With this arrangement, the worst-case
number of accesses is (log n).
We will store with each Skip List node an array named
forward
that stores
the pointers as shown in Figure 16.2(c). Position
forward[0]
stores a level 0
pointer,
forward[1]
stores a level 1 pointer, and so on. The Skip List object
includes data member
level
that stores the highest level for any node currently
in the Skip List. The Skip List stores a header node named
head
with
level
pointers. The
find
function is shown in Figure 16.3.
Searching for a node with value 62 in the Skip List of Figure 16.2(c) begins at
the header node. Follow the header node's pointer at
level
, which in this example
is level 2. This points to the node with value 31. Because 31 is less than 62, we
next try the pointer from
forward[2]
of 31's node to reach 69. Because 69 is
greater than 62, we cannot go forward but must instead decrement the current level
counter to 1. We next try to follow
forward[1]
of 31 to reach the node with
value 58. Because 58 is smaller than 62, we follow 58's
forward[1]
pointer
to 69. Because 69 is too big, follow 58's level 0 pointer to 62. Because 62 is not
less than 62, we fall out of the
while
loop and move one step forward to the node
with value 62.
